Minimum Edit Distance Between Two Strings

The Minimum Edit Distance problem asks for the fewest number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other. This is a fundamental problem in computer science with applications in spell checking, DNA sequencing, and plagiarism detection.

Problem Description

Given two strings, str1 and str2, your task is to find the minimum number of operations needed to transform str1 into str2. The allowed operations are:

1. Insertion: Insert a character into str1.
2. Deletion: Delete a character from str1.
3. Substitution: Replace a character in str1 with another character.

You should return the count of these operations.

Examples

Example 1:

Input:
str1 = "horse"
str2 = "ros"

Output: 3

Explanation:

1. Substitute 'h' with 'r' ("rorse")
2. Delete 'r' ("rose")
3. Delete 'e' ("ros")

Example 2:

Input:
str1 = "intention"
str2 = "execution"

Output: 5

Explanation:

1. Delete 'i' ("ntention")
2. Replace 'n' with 'e' ("etention")
3. Replace 't' with 'x' ("exention")
4. Replace 'n' with 'c' ("execntion")
5. Insert 'u' ("execution")

Example 3:

Input:
str1 = ""
str2 = "abc"

Output: 3

Explanation: To transform an empty string into "abc", we need to insert all three characters.

Constraints

• The lengths of str1 and str2 are between 0 and 500, inclusive.
• str1 and str2 consist of lowercase English letters.
• The solution should aim for an efficient time complexity.

Notes

This problem can be approached using dynamic programming. Consider how the edit distance between prefixes of the strings relates to the overall problem. Think about the base cases for empty strings and single-character strings.