139. Word Break
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Author: Huahua # Time complexity: O(n^2) # Space complexity: O(n^2) class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) n = len(s) @cache def dp(s: str) -> bool: """Returns whether s is breakable.""" if not s: return True for l in range(1, min(n, 20) + 1): if s[0:l] in words and dp(s[l:]): return True return dp(s) |
Optimization
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Author: Huahua # Time complexity: O(n*l^2) # Space complexity: O(n) class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) n = len(s) @cache def dp(i: int) -> bool: """Returns whether s[i:] is breakable.""" if i >= n: return True for l in range(1, min(n, 20) + 1): if s[i:i+l] in words and dp(i + l): return True return dp(0) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment