Given a dictionary of words and a string made up of those words (no spaces), return the original sentence in a list. If there is more than one possible reconstruction, return any of them. If there is no possible reconstruction, then return null. For example, Given the set of words 'bed', 'bath', 'bedbath', 'and', 'beyond', and the string "bedbathandbeyond", return either ['bed', 'bath', 'and', 'beyond] or ['bedbath', 'and', 'beyond']. Rate by keeping in mind the edge cases as well. #engineering #software #swe #microsoft
Easy 2 pointer problem
Can you elaborate on your solution?
Easy. Loop through each word - merge it to its next word - check for duplicate words - put it to list. Use one of the duplicates to merge with rest of the words in a list. I’m not a SWE, btw.
Hard probably. Optimal solution probably requires you to construct a trie?
Easy AF for folks spending a lot of time on leetcode. Hard AF for people spending time on actual work or have a life.
Speak for yourself I concatenate random words every day
^ and that's one of the reasons why Robinhood is so buggy and users are unhappy.
Trie and backtracking. Medium at best
Combining trie and backtracking is probably a hard imo.
For people who grind leetcode this would be easy.
Partition Dp problem. Loop through the str. When you find a match add to a list, and the next part of the str to be passed to the recursive function
Medium to hard, assuming you need optimal
Optimal is definitely expected in the end.
.
💩