Java DP O(nm) Time O(n) Space


  • 0
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[] dp = new int[n+1];
        for (int j=0;j<=m;j++) {
            int[] temp = new int[n+1];
            for (int i=0;i<=n;i++) {
                if (i==0) temp[i] = j; 
                else if (j==0) temp[i] = i;
                else if (word1.charAt(i-1) == word2.charAt(j-1)) temp[i] = dp[i-1];
                else temp[i] = 1 + Math.min(temp[i-1], dp[i]);
            }
            dp = temp;
        }
        return dp[n];
    }
    

  • 0
    M

    @compton_scatter
    Thanks for the solution.
    I have been trying to understand these kinds of solutions using a one-dimensional array but I haven't found an explanation yet. Could you please provide the explanation to this algorithm.


Log in to reply
 

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