Fork me on GitHub

One Edit Distance

Posted on

Description

Direction Solution (MLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int sizeS = s.size();
        int sizeT = t.size();
        
        vector<vector<int>> dp(sizeS + 1, vector<int>(sizeT + 1, 0));
        for (int i = 1; i <= sizeS; ++i) dp[i][0] = i;
        for (int j = 1; j <= sizeT; ++j) dp[0][j] = j;
        
        
        for (int i = 1; i <= sizeS; ++i){
            for (int j = 1; j <= sizeT; ++j) {
                int bias = (s[i - 1] == t[j - 1]) ? 0 : 1; 
                dp[i][j] = dp[i - 1][j - 1] + bias;
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            }
        }
        
        
        return dp[sizeS][sizeT] == 1;
    }
};

Unfortunately, this implementation can result in the memory excess in the last test case. So why don’t be naive, or let’s say, back to the origin.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) swap(s, t);
        int m = s.size(), n = t.size(), diff = m - n;
        if (diff >= 2) return false;
        else if (diff == 1) {
            for (int i = 0; i < n; ++i) {
                if (s[i] != t[i]) {
                    return s.substr(i + 1) == t.substr(i);
                }
            }
            return true;
        } else {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                if (s[i] != t[i]) ++cnt;
            }
            return cnt == 1;
        }
    }
};