16ms DP solution


  • 0
    P
        class Solution {
    public:
    	int minDistance(std::string word1, std::string word2) {
    		int nColCount = word1.size() + 1;
    		int nRowCount = word2.size() + 1;
    		int **pMatrix = (int **)malloc(sizeof(int *) * nRowCount);
    		for(int i = 0; i < nRowCount; ++i)
    		{
    			pMatrix[i] = (int *)malloc(sizeof(int) * nColCount);
    		}
    		for(int i = 0; i < nColCount; ++i)
    		{
    			pMatrix[0][i] = i;
    		}
    
    		for(int i = 0; i < nRowCount; ++i)
    		{
    			pMatrix[i][0] = i;
    		}
    
    		for(int i = 1; i < nRowCount; ++i)
    		{
    			for(int j = 1; j < nColCount; ++j)
    			{
    				if(word1[j - 1] == word2[i - 1])
    				{
    					pMatrix[i][j] = pMatrix[i - 1][j - 1];
    				}
    				else
    				{
    					int nMin = pMatrix[i - 1][j - 1] + 1;
    					if(pMatrix[i - 1][j] < nMin)
    					{
    						nMin = pMatrix[i - 1][j] + 1;
    					}
    					if(pMatrix[i][j - 1] < nMin)
    					{
    						nMin = pMatrix[i][j - 1] + 1;
    					}
    					pMatrix[i][j] = nMin;
    				}
    			}
    		}
    		return pMatrix[nRowCount - 1][nColCount - 1];
    	}
    };

Log in to reply
 

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