Java simple solution, 172ms


  • 0
    Y

    Just simple idea, use Set to store valid answers, but time and space complexity is high

    public class Solution {
        public boolean containWord(Set<String> once, Set<String> more, String word) {
            if (more.contains(word)) {
                return true;
            } else {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < word.length(); i++) {
                    sb.append(word.charAt(i));
                    if (once.contains(sb.toString()) && (once.contains(word.substring(i+1)) || containWord(once, more, word.substring(i+1)))) {
                        more.add(word);
                        return true;
                    }
                }
                return false;
            }
        }
    
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Set<String> once = new HashSet<>();
            Set<String> more = new HashSet<>();
            for (String word: words) {
                once.add(word);
            }
            List<String> ret = new ArrayList<>();
            for (String word: words) {
                if (containWord(once, more, word)) {
                    ret.add(word);
                }
            }
            return ret;
        }
    }
    

Log in to reply
 

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