Dynamic Programming - Recursive

Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
int minDistance(string word1, string word2) {
return helper(word1, word2, word1.size(), word2.size());
}

int helper(const string& s1, const string& s2, int m, int n) {
if (m == 0) return n;
if (n == 0) return m;
if (s1[m-1] == s2[n-1]) return helper(s1, s2, m-1, n-1);
return 1 + min({
helper(s1, s2, m-1, n-1),
helper(s1, s2, m , n-1),
helper(s1, s2, m-1, n)});
}

One Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isOneEditDistance(string s, string t) {
return helper(s, t, s.size(), t.size(), false);
}

bool helper(string& s, string& t, int m, int n, bool edited) {
if (m == 0) return (edited && n == 0) || (!edited && n == 1);
if (n == 0) return (edited && m == 0) || (!edited && m == 1);

if (s[m-1] == t[n-1]) return helper(s, t, m-1, n-1, edited);

if (edited) return false;

return
helper(s, t, m-1, n-1, true) || // replace
helper(s, t, m-1, n , true) || // delete
helper(s, t, m , n-1, true); // insert
}