This code gets WA, why?


  • 0
    Y
    int minDistance(string word1, string word2) {
    	int row = word1.size() + 1;
    	int col = word2.size() + 1;
    	int cost = 1;
    	vector<vector<int> > des(row, vector<int>(col));
    
    	for(int i = 0; i < row; i++)
    		des[i][0] = i;
    	for(int i = 0; i < col; i++)
    		des[0][i] = i;
    
    	for(int i = 1; i < row; i++){
    		for(int j = 1; j < col; j++){
    			if(word1[i-1] == word2[j-1]) cost = 0; //
    			des[i][j] = min(min(des[i-1][j]+1,des[i][j-1]+1),des[i-1][j-1]+cost);
    		}
    	}
    	cost = des[row-1][col-1];
    
    	return cost;
    }
    

    I know the mistake happened in this sentence: if(word1[i-1] == word2[j-1]) cost = 0;
    it seems logical, so I am confused.


  • 0
    H
        int minDistance(string word1, string word2) {
        int row = word1.size() + 1;
        int col = word2.size() + 1;
        int cost = 1;
        vector<vector<int> > des(row, vector<int>(col));
        
        for(int i = 0; i < row; i++)
            des[i][0] = i;
        for(int i = 0; i < col; i++)
            des[0][i] = i;
        
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                if(word1[i-1] == word2[j-1])
                    des[i][j] = des[i-1][j-1]; //
                else
                des[i][j] = min(min(des[i-1][j]+1,des[i][j-1]+1),des[i-1][j-1]+cost);
            }
        }
        cost = des[row-1][col-1];
        
        return cost;
    }

Log in to reply
 

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