#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int minDistance(string word1, string word2) {
int n=word1.length();
int m=word2.length();
vector<vector<int> > grid;
for(int i=0; i<n; i++){
vector<int> temp;
for(int j=0; j<m; j++){
temp.push_back(0);
}
grid.push_back(temp);
}
grid[0][0] = (word1[0]==word2[0]?0:1);
for(int i=1; i<n; i++){
if(word1[i]==word2[0]){
grid[i][0]=grid[i-1][0]+1;
}
}
for(int i=1; i<m; i++){
if(word1[0]==word2[i]){
grid[0][i]=grid[0][i-1]+1;
}
}
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
if(word1[i]==word2[j]){
grid[i][j]=grid[i-1][j-1];
}else{
grid[i][j]=std::min( grid[i-1][j-1] , std::min(grid[i-1][j],grid[i][j-1]) )+1;
}
}
}
return grid[n-1][m-1];
}
};
int main() {
// your code goes here
Solution s;
string s1("werwe");
string s2("wersdf656");
cout<<s.minDistance(s1,s2);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgU29sdXRpb24gewpwdWJsaWM6CiAgICBpbnQgbWluRGlzdGFuY2Uoc3RyaW5nIHdvcmQxLCBzdHJpbmcgd29yZDIpIHsKICAgICAgICBpbnQgbj13b3JkMS5sZW5ndGgoKTsKICAgICAgICBpbnQgbT13b3JkMi5sZW5ndGgoKTsKICAgICAgICB2ZWN0b3I8dmVjdG9yPGludD4gPiBncmlkOwogICAgICAgIGZvcihpbnQgaT0wOyBpPG47IGkrKyl7CiAgICAgICAgICAgIHZlY3RvcjxpbnQ+IHRlbXA7CiAgICAgICAgICAgIGZvcihpbnQgaj0wOyBqPG07IGorKyl7CiAgICAgICAgICAgICAgICB0ZW1wLnB1c2hfYmFjaygwKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBncmlkLnB1c2hfYmFjayh0ZW1wKTsKICAgICAgICB9CiAgICAgICAgZ3JpZFswXVswXSA9ICh3b3JkMVswXT09d29yZDJbMF0/MDoxKTsKICAgICAgICBmb3IoaW50IGk9MTsgaTxuOyBpKyspewogICAgICAgICAgICBpZih3b3JkMVtpXT09d29yZDJbMF0pewogICAgICAgICAgICAgICAgZ3JpZFtpXVswXT1ncmlkW2ktMV1bMF0rMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBmb3IoaW50IGk9MTsgaTxtOyBpKyspewogICAgICAgICAgICBpZih3b3JkMVswXT09d29yZDJbaV0pewogICAgICAgICAgICAgICAgZ3JpZFswXVtpXT1ncmlkWzBdW2ktMV0rMTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBmb3IoaW50IGk9MTsgaTxuOyBpKyspewogICAgICAgICAgICBmb3IoaW50IGo9MTsgajxtOyBqKyspewogICAgICAgICAgICAgICAgaWYod29yZDFbaV09PXdvcmQyW2pdKXsKICAgICAgICAgICAgICAgICAgICBncmlkW2ldW2pdPWdyaWRbaS0xXVtqLTFdOwogICAgICAgICAgICAgICAgfWVsc2V7CiAgICAgICAgICAgICAgICAgICAgZ3JpZFtpXVtqXT1zdGQ6Om1pbiggZ3JpZFtpLTFdW2otMV0gLCBzdGQ6Om1pbihncmlkW2ktMV1bal0sZ3JpZFtpXVtqLTFdKSApKzE7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGdyaWRbbi0xXVttLTFdOwogICAgfQp9OwoKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJU29sdXRpb24gczsKCXN0cmluZyBzMSgid2Vyd2UiKTsKCXN0cmluZyBzMigid2Vyc2RmNjU2Iik7Cgljb3V0PDxzLm1pbkRpc3RhbmNlKHMxLHMyKTsKCXJldHVybiAwOwp9