Skip to content

Instantly share code, notes, and snippets.

@s4553711
Created June 20, 2018 14:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save s4553711/9bccdc442fb5cdfba873687009ae98f0 to your computer and use it in GitHub Desktop.
Save s4553711/9bccdc442fb5cdfba873687009ae98f0 to your computer and use it in GitHub Desktop.
vector<vector<int> > C(s1.length() + 1, vector<int>(s2.length() + 1, 0));
// initial
for (int i = 1; i < s2.length() + 1; ++i) {
C[0][i] = C[0][i - 1] + s2[i - 1];
}
for (int i = 1; i < s1.length() + 1; ++i) {
C[i][0] = C[i - 1][0] + s1[i - 1];
}
for (int i = 1; i < s1.length() + 1; ++i) {
for (int j = 1; j < s2.length() + 1; ++j) {
if (s1[i - 1] == s2[j - 1]) {
C[i][j] = C[i - 1][j - 1];
} else {
// delete s1[i-1] or s2[j-1]
C[i][j] = min(C[i - 1][j] + s1[i - 1], C[i][j - 1] + s2[j - 1]);
}
}
}
return C[s1.length()][s2.length()];
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment