My solution: slight improvement by grouping dict words by length, and record max/min length.


  • 1
    A

    But I can't tell the complexity, any suggestion?

    /**
     * Group dict words by length: map<len, set<word>>.
     * Also record the maxLen and minLen for words on dict.
     * For s, try to find if the head is a word on dict; if so, 
     * recursively do the same for rest of string.
     * Head: substring with size from size minLen to maxLen, then
     * look up by len and from a set (constant performance).
     * Also use memoization to improve performance.
     * 
     * Complexity ~ (size of dict) * (lengh of s)?
     */
    
    // strings already checked
    private final Map<String, List<String>> memo = new HashMap<String, List<String>>();
    public List<String> wordBreak(String s, Set<String> dict) {
        // map of length and words; group dictionary words by length
        Map<Integer, Set<String>> lenWordsMap = new HashMap<Integer, Set<String>>();
        int minLen = Integer.MAX_VALUE;
        int maxLen = Integer.MIN_VALUE;
        for (String word : dict) {
            int len = word.length();
            if (len < minLen)
                minLen = len;
            if (len > maxLen)
                maxLen = len;
            Set<String> words = lenWordsMap.get(len);
            if (words == null) {
                words = new HashSet<String>();
                lenWordsMap.put(len, words);
            }
            words.add(word);
        }
        
        return wordBreakHelper(s, lenWordsMap, minLen, maxLen);
    }
    
    private List<String> wordBreakHelper(String s, Map<Integer, Set<String>> lenWordsMap,
        int minLen, int maxLen) 
    {
        List<String> results = memo.get(s);
        if (results != null)
            return results;
        
        results = new ArrayList<String>();
        if (s.length() < minLen)
            return results;
        for (int i = minLen; i <= maxLen && i <= s.length(); i++) {
            String head = s.substring(0, i);
            Set<String> words = lenWordsMap.get(i);
            if (words != null && words.contains(head)) {
                if (i == s.length()) {
                    results.add(head);
                    memo.put(s, results);
                    return results;
                }
                List<String> subResults = wordBreakHelper(s.substring(i, s.length()), 
                    lenWordsMap, minLen, maxLen);
                for (String subResult : subResults) {
                    String result = head + " " + subResult;
                    results.add(result);
                }
            }
        }
        
        memo.put(s, results);
        return results;
    }

Log in to reply
 

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