Snapchat: Word Finder


  • 0
    T

    We are given a list of words that have both 'simple' and 'compound' words in them. Write an algorithm that prints out a list of words without the compound words that are made up of the simple words.

    Input: chat, ever, snapchat, snap, salesperson, per, person, sales, son, whatsoever, what so.
    Output should be: chat, ever, snap, per, sales, son, what, so


  • 0

    @tfxcrunner88823 I have created a new subcategory and moved this question to the Snapchat subcategory. Thanks!


  • 1

    The idea . First we have to sort words by length. Then generate trie and put the words in it. Check in the trie if some word is compound.


  • 0
    T

    Any other ideas besides tries? I'm not very familiar with that data structure.


  • 1

    @tfxcrunner88823 you can use set

    def compositeWord(word,s):  
        if not word:
            return True  
        for prefix in (word[:i] for i in range(1, len(word) + 1)):
            if prefix in s:
                if compositeWord(word[len(prefix):], s) == True:
                    return True         
        s.add(word)    
        return False       
    
    def simpleWords(words):    
        s = set()   
        return [w for w in words if not compositeWord(w,s)]
    
    if __name__ == '__main__': 
        print(simpleWords(sorted(["chat","ever","snapchat","snap","salesperson","per","person","sales","son","whatsoever","what","so"],key=lambda s: len(s))))

  • 0
    T

    @elmirap wow great! I'm more of C guy, so I'll try to convert this. Thanks! If anyone else has code or solution ideas they want to post, that be awesome.


  • 0
    S

    Is the output correct?
    I believe, "son" should not be in the output because the simple word "so" is a part of the dictionary.


Log in to reply
 

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