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