Word Break | Mingzhe Du

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.- You may assume the dictionary does not contain duplicate words.

Example 1:

**Input:** s = "leetcode", wordDict = ["leet", "code"]
**Output:** true
**Explanation:** Return true because `"leetcode"` can be segmented as `"leet code"`.

Example 2:

**Input:** s = "applepenapple", wordDict = ["apple", "pen"]
**Output:** true
**Explanation:** Return true because `"`applepenapple`"` can be segmented as `"`apple pen apple`"`.
             Note that you are allowed to reuse a dictionary word.

Example 3:

**Input:** s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
**Output:** false

Recently, I am going to pick up my leetcode skills.

This problem that I still remember It token me more than two days to consider, but this time it was aced in 5 minutes, as well as just in nearly 1 line core code.

It seems like practising is really useful!

from functools import lru_cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @lru_cache(None)
        def dfs(s):
            return True if not s else any(dfs(s[len(word):]) for word in wordDict if s.startswith(word))
            
        return dfs(s)

Enjoy Reading This Article?