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.
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because
"leetcode"can be segmented as
Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because
"can be segmented as
"apple pen apple
". Note that you are allowed to reuse a dictionary word.
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)