6.7 String Editing

72. Edit Distance

Problem Description

Given two strings, you can delete, replace, or insert any character from either string. Find the minimum number of steps required to make the two strings identical.

Input and Output Example

Input consists of two strings, and the output is an integer representing the minimum number of steps.

Input: word1 = "horse", word2 = "ros"
Output: 3

In this example, one optimal sequence of edits is horse -> rorse -> rose -> ros.

Solution Explanation

Similar to problem 1143, we use a two-dimensional array dp[i][j], where dp[i][j] represents the minimum number of edits required to transform the first string up to position i and the second string up to position j.

• If the characters at position i and j are the same, then dp[i][j] = dp[i-1][j-1].
• If the characters differ:
  • The cost of modification is dp[i-1][j-1] + 1.
  • The cost of inserting at position i/deleting at position j is dp[i][j-1] + 1.
  • The cost of inserting at position j/deleting at position i is dp[i-1][j] + 1.

C++

int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0 || j == 0) {
                dp[i][j] = i + j;
            } else {
                dp[i][j] = dp[i - 1][j - 1] + (word1[i - 1] != word2[j - 1]);
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
            }
        }
    }
    return dp[m][n];
}

Python

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = i + j
            else:
                dp[i][j] = min(
                    dp[i - 1][j - 1] + int(word1[i - 1] != word2[j - 1]),
                    dp[i][j - 1] + 1,
                    dp[i - 1][j] + 1,
                )
    return dp[m][n]

650. 2 Keys Keyboard

Problem Description

Given the letter A, you can either copy all characters or paste the previously copied characters. Find the minimum number of operations needed to extend the string to the specified length.

Input and Output Example

The input is a positive integer representing the target length, and the output is an integer representing the minimum number of operations required.

Input: 3
Output: 3

In this example, one optimal sequence of operations is to copy once and paste twice.

Solution Explanation

Unlike typical dynamic programming problems that use addition or subtraction, this problem requires multiplication and division for state transitions because the paste operation doubles the length. We use a one-dimensional array dp, where dp[i] represents the minimum number of operations needed to extend the string to length i. For each position j, if j divides i, then length i can be achieved by operating on length j. The number of operations needed is equivalent to extending length j to length i / j. Thus, the recursive formula is dp[i] = dp[j] + dp[i / j].

C++

int minSteps(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        dp[i] = i;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                dp[i] = dp[j] + dp[i / j];
                // Early pruning since smaller j guarantees the minimal operations.
                break;
            }
        }
    }
    return dp[n];
}

Python

def minSteps(n: int) -> int:
    dp = [0] * 2 + list(range(2, n + 1))
    for i in range(2, n + 1):
        for j in range(2, floor(sqrt(i)) + 1):
            if i % j == 0:
                dp[i] = dp[j] + dp[i // j]
                # Early pruning since smaller j guarantees the minimal operations.
                break
    return dp[n]