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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.