Given two strings S1 and S2, we want to change S1 into S2 using the following operations:
- Insert any character anywhere into S1
- Delete any character of S1
- Change any character of S1 to another
We want to find the minimal number of operations to convert S1 into S2.
We can solve this problem using dynamic programming.
DP[i][j] = minimum number of operations to change the first i characters of S1 into the first j characters of S2.
DP[i][0] = i since we need to delete all these characters
DP[0][i] = i since we need to insert all these characters
When calculating DP[i][j] where i, j > 0
If S1[i] = S2[j] then DP[i][j] = DP[i-1][j-1], since we don’t need to do anything.
Otherwise we can either insert a new character, delete one, or replace one
If we replace one then: DP[i][j] = DP[i-1][j-1] + 1 (Don’t need to do anything)
If we insert one then: DP[i][j] = DP[i][j-1] + 1 (Insert a character to match i and j now)
If we delete one then: DP[i][j] = DP[i-1][j] + 1 (Delete ith character to match i-1 and j)
| int editDistance(string s1, string s2){ int n = s1.size(), m = s2.size(); vector<vector<int>> dp(n+1, vector<int>(m+1)); for(int i = 0; i <= n; i++)dp[i][0] = i; for(int i = 0; i <= m; i++)dp[0][i] = i; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(s1[i-1] == s2[j-1]){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1; } } } return dp[n][m]; } |