DP, O(n^2) Times, O(2n) Space.....Longest Common Seq


  • 0
    Z
    public int minDistance(String word1, String word2) {
            int l1 = word1.length();
            int l2 = word2.length();
            if (l1 < l2) return minDistance(word2, word1);
            int [] last = new int[l2 + 1];
            int [] cur = new int[l2 + 1];
            for (int i = 0; i < l1; i++) {
                for (int j = 0; j < l2; j++) {
                    if (word1.charAt(i) == word2.charAt(j)) cur[j + 1] = last[j] + 1;
                    else cur[j + 1] = Math.max(cur[j], last[j + 1]);
                }
                int[] tmp = cur;
    	    cur = last;
    	    last = tmp;
            }
            return l1 + l2 - last[l2] * 2;
        }
    

Log in to reply
 

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