Java solution using DP


  • 2
    Q

    public int minDistance(String word1, String word2) {
    if(word1 == null || word2 == null) {
    return Math.max(word1.length(), word2.length());
    }

            word1 = "#" + word1;
    		word2 = "#" + word2;
    		int[][] Distance = new int[word1.length()][word2.length()];
            // Initialization
            for(int i = 0; i < word1.length(); i++) {
            	Distance[i][0] = i;
            }
            
            for(int j = 0; j < word2.length(); j++) {
            	Distance[0][j] = j;
            }
            
            // Recurrence Relation:
            for(int i = 1; i < word1.length(); i++) {
            	for(int j = 1; j < word2.length(); j++) {
            		
            		Distance[i][j] = Math.min(Distance[i-1][j], Distance[i][j-1]) + 1;
            		
            		int temp = 0;
            		if (word1.charAt(i) == word2.charAt(j)) {
            			temp =  Distance[i-1][j-1];
            		} else {
            			temp = Distance[i-1][j-1] + 1;
            		}
            		
            		Distance[i][j] = Math.min(Distance[i][j], temp);
            	}
            }
            
            return Distance[word1.length()-1][word2.length()-1];
    }

  • 0
    Q

    I just change the item:
    temp = Distance[i-1][j-1] + 2 (I thought the cost should be 2) to temp = Distance[i-1][j-1] + 1
    Accepted!


  • 0
    X

    I think the distance from [i-1][j-1] to [i][j] is 1(insert or replace, cause we don't need to edit word2[j]). I used the solution above to judge and accepted as well.


Log in to reply
 

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