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!


  • 2

    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.


  • 1
    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.


  • 0
    K

    @tfxcrunner88823 Should "son" be printed? Since "so" is in the output


Log in to reply
 

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