Java DP, keep index of each count. Beat 97%


  • 0
    G
    public int minDistance(String word1, String word2) {
        int n = word1.length() < word2.length() ? word1.length() : word2.length();
        int[] counts = new int[n + 1];  
        counts[0] = -1;
        int maxCount = 0;
        
        for(int i = 0; i < word1.length(); i++){
            for(int t = maxCount + 1; t > 0; t--){
                int start = counts[t - 1] + 1;
                int end = -1;
                if(t == maxCount + 1)
                    end = word2.length();
                else
                    end = counts[t];
                
                for(int j = start; j < end; j++){
                    if(word1.charAt(i) == word2.charAt(j)){
                        counts[t] = j;
                        
                        if(t == maxCount + 1)
                            maxCount++;
                        
                        break;
                    }
                }
            }
            
            if(maxCount == n)
                break;
        }
        
        return word1.length() + word2.length() - 2 * maxCount; 
    }

Log in to reply
 

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