Medium

Word Break

061

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

EXAMPLES

Example 1

Input
{
  "s": "leetcode",
  "wordDict": [
    "leet",
    "code"
  ]
}

Output
true

FUNCTION SHAPE

s: stringwordDict: stringArray→bool

SOLUTION NOTE

Try all prefixes starting at i. If prefix is in dictionary and rest can be segmented, return True.

Reveal reference solution +

pythonREFERENCE

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

    @cache
    def dp(i):
        if i == len(s):
            return True
        for j in range(i + 1, len(s) + 1):
            if s[i:j] in words and dp(j):
                return True
        return False

    return dp(0)

TimeO(n² × m)

SpaceO(n)

Open on LeetCode ↗