Java DP Solution(seems simple)


  • 0
    D
    public static int minDistance(String word1,String word2){//动态规划
    	int[][] table = new int[word1.length()+1][word2.length()+1];
    	int m = word1.length();
    	int n = word2.length();
    	for(int i = 1;i<=m;i++){
    		for(int j = 1;j<=n;j++){
    			if(word1.charAt(i-1)==word2.charAt(j-1)){
    				table[i][j] = table[i-1][j-1]+1;
    			}
    			else{
    				table[i][j] = Math.max(table[i-1][j], table[i][j-1]);
    			}
    		}
    	}
    	return n+m-table[m][n]*2;
    }

  • 0
    D

    @DoubleGOO said in Java DP Solution(seems simple):

    public int minDistance(String word1,String word2){//动态规划
    int[][] table = new int[word1.length()+1][word2.length()+1];
    int m = word1.length();
    int n = word2.length();
    for(int i = 1;i<=m;i++){
    for(int j = 1;j<=n;j++){
    if(word1.charAt(i-1)==word2.charAt(j-1)){
    table[i][j] = table[i-1][j-1]+1;
    }
    else{
    table[i][j] = Math.max(table[i-1][j], table[i][j-1]);
    }
    }
    }
    return n+m-table[m][n]*2;
    }


Log in to reply
 

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