Recursive, DP easy to read solution 7 ms


  • 0
    M

    Space and runtime O(nm)

    public int minDistance(String word1, String word2) {
        return minDistance(word1,word2,0,0,new int [word1.length()][word2.length()]);
    }
    
    private int minDistance(String word1, String word2, int i1, int i2, int [][] cache){
        if(i1 == word1.length()) return word2.length()-i2;
        else if(i2 == word2.length()) return word1.length()-i1;
        if(cache[i1][i2] != 0) return cache[i1][i2];
        
        if(word1.charAt(i1) == word2.charAt(i2))
            cache[i1][i2] = minDistance(word1,word2,i1+1,i2+1,cache);
        else {
            cache[i1][i2] = Math.min(minDistance(word1,word2,i1,i2+1,cache),Math.min(
            minDistance(word1,word2,i1+1,i2,cache), minDistance(word1,word2,i1+1,i2+1,cache))) + 1;
        }
        return cache[i1][i2];
    }

Log in to reply
 

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