My DP c++ solution


  • 0
        int minDistance(string str1, string str2) {
        if(str1.empty()) return str2.length();
        if(str2.empty()) return str1.length();
        int g_a[1000][1000];
            g_a[0][0] = str1[0] == str2[0] ? 0 : 1;
    	for (int i = 1; i < str1.length(); i++) {
    		g_a[i][0] = str1[i] == str2[0] ? i : g_a[i - 1][0] + 1;
    	}
    	for (int j = 1; j < str2.length(); j++) {
    		g_a[0][j] = str1[0] == str2[j] ? j : g_a[0][j-1] + 1;
    	}
    	for (int i = 1; i < str1.length(); i++) {
    		for (int j = 1; j < str2.length(); j++) {
    			if (str1[i] == str2[j])
    				g_a[i][j] = g_a[i - 1][j - 1];
    			else g_a[i][j] = min(g_a[i - 1][j], min(g_a[i][j - 1], g_a[i - 1][j - 1])) + 1;
    		}
    	}
    	return g_a[str1.length()-1][str2.length()-1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.