Accepted 32ms c++ DP solution.


  • 1
    class Solution {
    public:
        int minDistance(std::string word1, std::string word2) {
    		int len1 = word1.size(), len2 = word2.size();
    		if (!len1)
    			return len2;
    		if (!len2)
    			return len1;
    		std::vector<std::vector<int> > flag(len1 + 1, std::vector<int>(len2 + 1));
    		for (int row = 0; row <= len1; ++row)
    			flag[row][0] = row;
    		for (int col = 0; col <= len2; ++col)
    			flag[0][col] = col;
    		for (int row = 1; row <= len1; ++row)
    			for (int col = 1; col <= len2; ++col)
    				flag[row][col] = std::min(std::min(flag[row - 1][col] + 1, flag[row][col - 1] + 1), 
    					flag[row - 1][col - 1] + (word1[row - 1] == word2[col - 1] ? 0 : 1));
    		}
    		return flag[len1][len2];
        }
    };

Log in to reply
 

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