Click here to see the full article post
Thank you for the solution. The question states "the longest word in words that can be built one character at a time by other words". However, it did not explicitly specify that the previous word should be prefix. This made me assume ["d","ld","rld","orld", "world"] should be valid sequence.
I think this question should be stated correctly since I misunderstood we can add char at any position of previous str!
The description of this problem is not clear. I have to guess from the example that "previous word should be prefix"
Trie = lambda: collections.defaultdict(Trie) trie = Trie() for i, word in enumerate(words): reduce(dict.__getitem__, word, trie)[True] = i
One doesn't need to use a trie to achieve the same time & space complexities as in the second solution: we can just sort on word length and lexicographical ordering and then add words to a hashset if the word without last letter is in the set. In this case we can just update our solution every time we find a longer word which can be added to the set and because of the sorting on lexicographical ordering we will have the smallest lexicographical solution in the end.
@snailandmail sort? Thats nlogn comparisons for each character.
With trie, it's O(no. of character in all words). Its way faster.
Java solution for Approach #2 doesn't work. There is an issue in 'if' conditions in dfs method. The approach is nice though.
@soboltv Can you explain further? All solutions in every article have always been checked to get AC with the leetcode test cases. Is there some test case that fails?
Can some one explain what the Python solution does in the beginning?
This part -
Trie = lambda: collections.defaultdict(Trie)
trie = Trie()
END = True
for i, word in enumerate(words): reduce(dict.__getitem__, word, trie)[END] = i
It's for building Trie. The lambda is equivalent to this
def Trie(): return defaultdict(Trie)
So Trie() returns a default dict which when the key bening accessed is absent, it will create a Trie for the key.
reduce build trie for each character. By calling trie's (defaultdict) accessor method.
reduce returns the leave trie, and it sets its
True key to be the word's index for later use.
@derek3 You are right, although complexity will be O(nlogn * M) where n is number of words and M is maximum word length when proposed complexity is O(n * M).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.