跳至主要内容

6.7 字符串編輯

72. Edit Distance​

題目描述​

給定兩個字符串，已知你可以刪除、替換和插入任意字符串的任意字符，求最少編輯幾步可以將兩個字符串變成相同。

輸入輸出範例​

輸入是兩個字符串，輸出是一個整數，表示最少的步驟。

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

在這個範例中，一種最優編輯方法是 horse -> rorse -> rose -> ros。

題解​

類似於題目 1143，我們使用一個二維陣列 dp[i][j]，表示將第一個字符串到位置 i 為止，和第二個字符串到位置 j 為止，最多需要幾步編輯。

  • 當第 i 位和第 j 位對應的字符相同時，dp[i][j] = dp[i-1][j-1]；
  • 當兩者對應的字符不相同時：
    • 修改的消耗為 dp[i-1][j-1] + 1；
    • 插入 i 位置/刪除 j 位置的消耗為 dp[i][j-1] + 1；
    • 插入 j 位置/刪除 i 位置的消耗為 dp[i-1][j] + 1。
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];
}

650. 2 Keys Keyboard​

題目描述​

給定一個字母 A，已知你可以每次選擇複製全部字符，或者粘貼之前複製的字符，求最少需要幾次操作可以把字符串延展到指定長度。

輸入輸出範例​

輸入是一個正整數，代表指定長度；輸出是一個整數，表示最少操作次數。

Input: 3
Output: 3

在這個範例中，一種最優的操作方法是先複製一次，再貼上兩次。

題解​

不同於以往通過加減實現的動態規劃，這裡需要乘除法來計算位置，因為粘貼操作是倍數增加的。我們使用一個一維陣列 dp，其中位置 i 表示延展到長度 i 的最少操作次數。對於每個位置 j，如果 j 可以被 i 整除，那麼長度 i 就可以由長度 j 操作得到，其操作次數等價於把一個長度為 j 的 A 延展到長度為 i/j。因此我們可以得到遞推公式 dp[i] = dp[j] + dp[i/j]。

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];
                // 提前剪枝，因為j從小到大，因此操作數量一定最小。
                break;
            }
        }
    }
    return dp[n];
}