139. Medium

Word Break🔗

MediumDynamic ProgrammingTrieHash TableAmazonGoogleMicrosoftMeta

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Optimal Approach — Bottom-Up Dynamic Programming

O(n * m * k) Time

🧱

Building from the End

Time O(n * m * k)Space O(n)

We can solve this efficiently by working backward! For each character index, if we find a dictionary word that matches the characters starting exactly there, we check if the rest of the string can be broken down. If so, this index is also valid!

1Initialize a dp array of size len(s) + 1 with False. Set the base case dp[len(s)] = True (an empty string is always valid).
2Loop backward from the end of the string to the start. For each index i, try matching every word w in the dictionary.
3If the word fits and matches perfectly starting from index i, look ahead: does dp[i + len(w)] evaluate to True? If yes, set dp[i] = True and break early.
4When we reach index 0, dp[0] will store our answer!

READYPress ▶ or step forward to begin.

✓

—

String (s)

Dictionary (comma separated)

Executing Code

class Solution:

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

        dp = [False] * (len(s) + 1)

        dp[len(s)] = True

        for i in range(len(s) - 1, -1, -1):

            for w in wordDict:

                if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:

                    dp[i] = dp[i + len(w)]

                if dp[i]:

                    break

        return dp[0]

Discussion

…

Loading comments…

LeetMotion