# Snapchat: Word Finder

• 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

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

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

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

• @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
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))))

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

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

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

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