Java DP solution O(mn) time, O(n) space, beats 97%.


  • 1
    S
    public int minDistance(String word1, String word2) {
            if (word1.length() == 0) {
                return word2.length();
            }
            if (word2.length() == 0) {
                return word1.length();
            }
            int l1 = word1.length();
            int l2 = word2.length();
            int[] minDist = new int[l2 + 1];
            for (int j = 0; j <= l2; j++) {
                minDist[j] = j;
            }
            
            char[] chs1 = word1.toCharArray();
            char[] chs2 = word2.toCharArray();
            int prev;//store minDist[i - 1][j -1]
            for (int i = 1; i <= l1; i++) {
                minDist[0] = i - 1;
                prev = minDist[0];
                for (int j = 1; j <= l2; j++) {
                    int temp = minDist[j];
                    if (chs1[i - 1] == chs2[j - 1]) {
                        minDist[j] = prev;
                    } else {
                        minDist[j] =  Math.min(minDist[j], Math.min(prev, minDist[j - 1])) + 1;
                    }
                    prev = temp;
                }
            }
            return minDist[l2];
        }

Log in to reply
 

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