Easy to understand recursive/DP solution, beats 99.6%


  • 3
    B
    public class Solution {
        int[][] dp;
        
        public int minDistance(String word1, String word2) {
    	dp = new int[word1.length()][word2.length()];
    	    
            return minDistanceHelper(word1, word2, 0, 0);
        }
        
        private int minDistanceHelper(String word1, String word2, int index1, int index2) {
            if (index1 == word1.length()) return word2.length() - index2;
            if (index2 == word2.length()) return word1.length() - index1;
    	    
    	if (dp[index1][index2] > 0) return dp[index1][index2];
            
            int result;
            if (word1.charAt(index1) == word2.charAt(index2)) {
                result = minDistanceHelper(word1, word2, index1+1, index2+1);
            } else {
                // replace char
                result = 1 + minDistanceHelper(word1, word2, index1+1, index2+1);
                
                // delete char from word1
                result = Math.min(result, 1 + minDistanceHelper(word1, word2, index1+1, index2));
                
                // delete char from word2
                result = Math.min(result, 1 + minDistanceHelper(word1, word2, index1, index2+1));
            }
            
    	dp[index1][index2] = result;
    	return result;
        }
    }

Log in to reply
 

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