题目简介:
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1:
1 | 输入: s = "leetcode", wordDict = ["leet", "code"] |
示例 2:
1 | 输入: s = "applepenapple", wordDict = ["apple", "pen"] |
示例 3:
1 | 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] |
思路:
使用动态规划的思想,dp[i]
代表0 ~ i - 1
的字符串能否被成功拆分。
先将字典中的单词存入哈希表,方便查找。
我们可以将0 ~ i - 1
的字符串可以分为0 ~ j - 1
和j ~ i - 1
,所以dp[i]
取决于dp[j]
和s.substr(j, i - j)
这个字符串是否为单词表中的单词。
所以切割点j
的遍历范围每次都为0 ~ i - 1
。
tip:
- 可以在初始化时多分配一个空间,
dp[0] = true
,代表空串时成功分割单词。
代码如下:
1 | class Solution { |