< Back




139. Word Break

Given a list of words and a string, we're asked to determine if the string can be broken up into
multiple strings without any leftover characters using the list of words.

My natural intuition for substring problems is to use two pointers, i and j, to reference the
substring we're looking at and to maintain state. Because this section is dynamic programming, I
know I'll need to maintain a memoization table of previously solved problems / states.

With our memoization table, T, T[0] will default to True. This represents the empty string which
is always part of our set, even the empty set. All other parts of table are False. Each index in
the table represents whether or not the string can be split up into multiple strings using the
word dictionary at that index, i. For instance, in "leetcode" with dictionary ["leet", "code"],
index T[4] == True.

Our second pointer, j, we're going to iterate through the string with, and it will represent the end
of the substring. Our first pointer, i, will restart at 0 and iterate to j - 1 during each step of
the algorithm. During each step, we'll check to see if string[i:j] is in the word dictionary, and
mark T[j] == True if so. We'll only do this if the previous assessment of the previous substring was
also True, meaning T[i] needs to equal True. This allows our answer to build upon previous
solutions, because we wouldn't be able to truly split the string if we only considered one substring
in a vacuum.

The solution is as follows:


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n, words = len(s), set(wordDict)
        T = [False] * (n + 1)
        T[0] = True

        for j in range(1, n + 1):
            for i in range(j):
                if T[i] and s[i:j] in words:
                    T[j] = True
                    break

        return T[-1]


_ Time Complexity:

  O(n^3 + m * k) - Our nested for loop iterates n^2 times, and we do a substring operation which
  takes n time. Also, converting our list to a set will take m * k time.

_ Space Complexity:

  O(n + m * k) - We create a set from the input, and we maintain a memoization table of size n.