72. Edit Distance

Given two wordsword1andword2, find the minimum number of steps required to convertword1toword2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

S: DP O(MN)

dist[i][j]表示word1[0]-word1[i]与word2[0]=word2[j]匹配所用的最小operation

若word1[i] = word2[j] dist[i][j] = dist[i-1][j-1]

否则取replace：dist[i-1][j-1]+1, delete: dist[i-1][j]+1, insert: dist[i][j-1]+1的最小值

    int minDistance(string word1, string word2) {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<vector<int>> dist(n1 + 1, vector<int>(n2 + 1, 0));
        for (int i = 1; i < n1 + 1; ++i) {
            dist[i][0] = i;
        }
        for (int i = 1; i < n2 + 1; ++i) {
            dist[0][i] = i;
        }
        for (int i = 1; i < n1 + 1; ++i) {
            for (int j = 1; j < n2 + 1; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dist[i][j] = dist[i - 1][j - 1];
                } else {
                    dist[i][j] = min(dist[i - 1][j - 1] + 1, dist[i - 1][j] + 1); //delete
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1); //insert, 在dist[i][j-1]的基础上在word1[i],word2[j-1]后插入word2[j]
                }
            }
        }
        return dist[n1][n2];
    }

161. One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

S: for loop O(n)

用usedOne记录是否用过一次edit

    bool isOneEditDistance(string s, string t) {
        int size1 = s.size();
        int size2 = t.size();
        if (abs(size1 - size2) > 1) {
            return false;
        }
        if (size1 < size2) {
            return isOneEditDistance(t, s);
        }
        bool hasOneEdit = false;
        int i = 0, j = 0;
        for (; i < size1 && j < size2; ++i, ++j) {
            if (s[i] != t[j]) {
                if (hasOneEdit) {
                    return false;
                } else {
                    hasOneEdit = true;
                    if (size1 > size2) {
                        j--;
                    }
                }
            }
        }
        return (hasOneEdit && i == size1 && j == size2) || (!hasOneEdit && i < size1);
    }