Very fast run time (Java)


  • 0
    T

    public class Solution {

    private int getMaxLength(Set<String> dict){
        int maxLength = 0;
        for(String word : dict){
            maxLength = Math.max(maxLength, word.length());            
        }
        return maxLength;
    }
    
    private int getMinLength(Set<String> dict){
        int minLength = 0;
        for(String word : dict){
            minLength = Math.min(minLength, word.length());
        }
        return minLength;
    }
    
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0){
            return false;
        }
        int maxLength = getMaxLength(wordDict);
        int minLength = getMinLength(wordDict);
        boolean[] canBreak = new boolean[s.length()+1];
        canBreak[0] = true;
        for(int i = 1; i <= s.length(); i++){
            canBreak[i] = false;
            for(int lastWordLength = minLength; lastWordLength <= maxLength && lastWordLength <= i; lastWordLength++){
                if(!canBreak[i - lastWordLength]){
                    continue;
                }
                String word = s.substring(i - lastWordLength, i);
                if(wordDict.contains(word)){
                    canBreak[i] = true;
                }
            }
        }
        return canBreak[s.length()];
    }
    

    }


Log in to reply
 

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