Leetcode: Word break
Given a string
s and a list of
True if the string can be constructed from any combination of the words and
False otherwise. The alphabet contains only lowercase English characters.
My initial idea was to replace all occurrences of a
word in the string
s. The problem with this approach is that a string
aabb with the words
['ab'] is considered valid, while it is not. I then tried on adding breaking characters (
.) to prevent this. It worked although very slowly.
My next approach was to start only from the beginning and remove the current
s if it was the prefix. The advantage is that this alrogrithm is relatively straightforward. The disadvantage is that it is relatively time-intensive. The same words will be checked over and over again.
Adding memoization speeds up the solution by quite a bit. Here, we initialize a
dictionary, that contains all previously seen and invalid or valid substrings. Before going into the recursion, we check whether the word was already seen and if it was, we return the previously computed value.
Runtime: 75 ms, faster than 25.22% of Python3 online submissions for Word Break. Memory Usage: 14.2 MB, less than 14.55% of Python3 online submissions for Word Break.A good explanation on dynamic programming and memoization can be found here.