Easy to understand DP solution w/ two hash sets


  • 0
    B

    The idea is maintain two hash sets :

    1. dict : all input words
    2. ccDict : all words that can be concatenated by shorter words in dict, these words are by-product of exploration of previous words.
    public class Solution {
        int minLen = Integer.MAX_VALUE;
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Set<String> dict = new HashSet<String>();
            for (String str : words) {
                if (str.length() == 0) continue;
                dict.add(str);
                minLen = Math.min(minLen, str.length());
            }
            Set<String> ccDict = new HashSet<>();
            List<String> ret = new ArrayList<>();
            for (String word : words) {
                if (isConcatWord(word, dict, ccDict)) {
                    ret.add(word);
                }
            }
            return ret;
        }
        public boolean isConcatWord(String word, Set<String> dict, Set<String> ccDict) {
            if (ccDict.contains(word)) {return true;}
            int len = word.length();
            for (int i = minLen; i <= len - minLen; i++) {
                String part1 = word.substring(0, i);
                String part2 = word.substring(i);
                if (dict.contains(part1) && (dict.contains(part2) || isConcatWord(part2, dict, ccDict))) {
                    ccDict.add(word);
                    return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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