刷题笔记0x09:单词拆分
题目分析
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。https://leetcode-cn.com/problems/word-break/
这个题目一开始被我误解成是判断列表中的字符串是否都是s
的子串,最后看到官方示例才纠正回来~
可以发觉,这个题目我们是要找出断点打断字符串s
,让打断后的各个单词都在单词列表中。
下面分析一下,如果我们有一个长度为i
的字符串,那么假设dp[j]
表示字符串到j
位置的子字符串是否符合题目条件,可以得出,如果dp[i]
也就是长度为i
的原字符串s
符合条件,那么一定有一个0 < j < i
的情况下,dp[j]
符合条件,并且,剩下的j
到i
的部分是在单词列表里面的。
通过分析我们发现这是一个可以用动态规划解决的问题,状态转移方程为:
// 伪代码
dp[i] = dp[j] and (s[j:i] in wordDict)
代码实现
在具体代码中,我们设dp
数组长度为s长度加一,dp[0]
设为真做初始条件,从i=1
开始迭代。
impl Solution {
pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
let length = s.chars().count();
let mut dp: Vec<bool> = vec![false; length + 1];
dp[0] = true;
for i in 1..=length {
for j in 0..i {
let word = s.as_str()[j..i].to_string();
if dp[j] && word_dict.contains(&word) {
dp[i] = true;
break;
}
}
}
dp[length]
}
}
最后成功超越100%,不过这和Leetcode上用Rust
刷题的少也有关系。
优化
我们的代码还有优化的空间,不过由于现在耗时四舍五入0ms了,为了展示差别,用Python
演示下(这样感觉Python很没有排面啊:
先上个普通Python版:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
length = len(s)
dp = [False] * (length + 1)
dp[0] = True
for i in range(1, length + 1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]
由于线性表查找时间复杂度为O(N)
,而哈希表查找时间复杂度为O(1)
,所有我们利用字典生成式将原本的单词列表转成哈希结构的字典:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
length = len(s)
dp = [False] * (length + 1)
dp[0] = True
wordDict = {key: value for value, key in enumerate(wordDict)}
for i in range(1, length + 1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]
快了一丢丢~
评论区也有先求出wordDict
中最长单词长度maxWordLength
,仅遍历当前i
位置向前maxWordLength
的元素,以减少循环次数,不过我试了几次运行时间没有显著提升。