Java DFS Solution, 103 ms


  • 0
    1. Use Set to store the dictionary.
    2. Check each word to see whether it can be broken into different words.
    3. Use a set to store those won't work.
    public class Solution {
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Set<String> dict = new HashSet<String>();
            int n = words.length;
            List<String> res = new ArrayList<String>();
            if(n <= 1)return res;
            for(int i = 0; i < n; i++){
                dict.add(words[i]);
            }
            Set<String> invalid = new HashSet<String>();
            for(int i = 0; i < n; i++){
                if(canSplit(words[i],invalid,dict,0)){
                    res.add(words[i]);
                }
            }
            return res;
        }
        
        public boolean canSplit(String word, Set<String> invalid, Set<String> dict, int cur){
            int n = word.length();
            if(cur > 0 && dict.contains(word))return true;
            if(invalid.contains(word))return false;
            for(int i = 1; i < n; i++){
                String subWord = word.substring(0,i);
                if(dict.contains(subWord)){
                    if(canSplit(word.substring(i), invalid, dict, cur+1)){
                        return true;
                    }
                }
            }
            if(!dict.contains(word))invalid.add(word);
            return false;
        }
    }
    

Log in to reply
 

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