having been troubled by this for a long time.... here is my pretty short java code beats 78% quite easy no comlicated data structure


  • 3
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> list = new ArrayList<>();
            Set<String> dictionary = new HashSet<>();
            for(String string : words) dictionary.add(string);
            for(String word:words) {
                dictionary.remove(word);
                if(check(word,dictionary)) list.add(word);
                dictionary.add(word);
            }
            return list;
        }
        
        private boolean check(String word,Set<String> dictionary) {
            if(dictionary.contains(word)) return true;
            int i = word.length() - 1;
            while(i >= 1) {
                if(dictionary.contains(word.substring(0,i)) && check(word.substring(i),dictionary)) return true;
                i--;
            }
            return false;
        }

  • 1
    K

    amazing job, dude!
    That is really helpful.


  • 1

    thanks a lot


  • 0
    C

    thanks for your nice solution


  • 0
    W

    Nice solution!
    I implemented it in python 3 and it beats 100%!
    Here it is.

    class Solution:
        def findAllConcatenatedWordsInADict(self, words):
            """
            :type words: List[str]
            :rtype: List[str]
            """
            res = []
            words_dict = set(words)
            for word in words:
                words_dict.remove(word)
                if self.check(word, words_dict) is True:
                    res.append(word)
                words_dict.add(word)
            return res
        
        def check(self, word, d):
            if word in d:
                return True
            
            for i in range(len(word),0, -1):
                if word[:i] in d and self.check(word[i:], d):
                    return True
            return False
    

Log in to reply
 

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