0139. 单词拆分

0139. 单词拆分 #

  • 标签:字典树、记忆化搜索、哈希表、字符串、动态规划
  • 难度:中等

题目大意 #

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict。要求:判断 s 是否能被空格拆分为一个或多个在字典中出现的单词。

说明:

  • 拆分时可以重复使用字典中的单词。
  • 可以假设字典中没有重复的单词。

解题思路 #

可以用动态规划求解。

s 能否拆分为单词表的单词,可以分解为:

  • 前 i 个字符构成的字符串,能否分解为单词。
  • 剩余字符串,能否分解为单词。

可以定义状态 dp[i] 表示:长度为 i 的字符串 s[0: i] 能否拆分成单词,如果为 True 则表示可以拆分,如果为 False 则表示不能拆分。

转移方程可以表示为:如果 dp[j] 可以拆分为单词,并且字符串 s[j: i] 出现在字典中,则 dp[i] = True

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        size = len(s)
        dp = [False for _ in range(size + 1)]
        dp[0] = True
        for i in range(size + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
        return dp[size]
本站总访问量  次  |  您是本站第  位访问者