Very Concise Java Solution


  • 0

    I use a helper function that is called recursively to determine if a word belongs to a given list. Before calling the helper function, the target word is removed from the list (otherwise it always returns true). After checking, I add it back to the list.

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new LinkedList<>();
        if(words.length == 0)   return res;
        HashSet<String> set = new HashSet<>();
        for(int i = 0; i < words.length; i++)
            set.add(words[i]);
        for(String word : words) {
            set.remove(word);
            if(canForm(word, set) && word.length() != 0)
                res.add(word);
            set.add(word);
        }
        return res;
    }
    
    public boolean canForm(String word, HashSet<String> set) {
        if(set.contains(word) || word.length()==0)  return true;
        for(int i = 1; i <= word.length(); i++) {
            String subWord = word.substring(0, i);
            if(set.contains(subWord)) {
                String restWord = word.substring(i);
                if(canForm(restWord, set))
                    return true;
            }
        }
        return false;
    }
    

Log in to reply
 

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