202401302224
tags: #dp

from functools import lru_cache
class Solution:
	def wordBreak(self, s: str, wordDict: List[str]) -> bool:
		@lru_cache(maxsize=None)
		def solve(index):
			if index == len(s):
				return True
			if index > len(s):
				return False
			for word in wordDict:
				if index + len(word) <= len(s) and s[index : index + len(word)] == word:
					if solve(index + len(word)) == True:
						return True
			return False
		return solve(0)

Reference

https://leetcode.com/problems/word-break/