【Leetcode】139.拆分词句

加个“星标”，一起坚持学习

题目描述

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

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

输入: s ="leetcode", wordDict = ["leet","code"]

输出:true

解释: 返回true因为"leetcode"可以被拆分成"leet code"。

示例 2：

输入: s ="applepenapple", wordDict = ["apple","pen"]

输出:true

解释: 返回true因为"applepenapple"可以被拆分成"apple pen apple"。

注意你可以重复使用字典中的单词。

示例 3：

输入: s ="catsandog", wordDict = ["cats","dog","sand","and","cat"]

输出:false

暴力搜索

这道题最开始我们想的肯定是每个字符遍历， 然后去看是不是在wordDict里面。而wordDict是一个list，查找是o(N)的时间复杂度，需要把这个时间复杂度先降下来，用Set把每次查找的时间复杂度降到o(1)。

怎么去check一个字符串wordDict能不能被组成，一个很朴素的想法就是把每个字符串分作两段，然后递归。比如如下代码。

publicclassSolution{

publicbooleanwordBreak(String s, List wordDict){

returnhelper(s,newHashSet(wordDict),);

}

publicbooleanhelper(String s, Set wordDict,intstart){

if(start == s.length()) {

returntrue;

}

for(intend = start +1; end

if(wordDict.contains(s.substring(start, end))

&& helper(s, wordDict, end)) {

returntrue;

}

}

returnfalse;

}

}

很显然这种思路是行不通的，因为时间复杂度太高，有兴趣的同学可以试一下。

时间复杂度: O(n^n)

空间复杂度：O(n)

记忆化搜索

重复计算太多。哪里重复了？举个例子：

输入: s ="AAAleetcodeB", wordDict = ["leet","code","A","AA","AAA"]

for循环中：

首次递归: s ='A'+ helper('AAleetcodeB'), 最终检查不符合;

二次递归: s ='AA'+ helper('AleetcodeB'), 最终检查不符合;

三次递归: s ='AAA'+ helper('leetcodeB'), 最终检查不符合;

发现没, 上面每一次都重复计算了。

节省时间的办法也很自然：要是我们能把搜索过的内容记下来就好了。记忆有两种办法可供参考：

动态规划

记忆化数组进行搜索

动态规划

我们先看动态规划，动态规划其实很好理解，最重要的是状态转移方程。不懂的同学，可以手动模拟一遍基本就理解了。

dp[i]表示[0, i] 子串是否能够由wordDict组成

dp[i] = 对于任意j, dp[j] && wordDict 包含 s[j + 1, i]，其中j 属于区间 [0, i] 。

模拟一下动态规划的过程是:

输入: s ="AAAleetcodeB", wordDict = ["leet","code","A","AA","AAA"]

dp[] =true// 初始化.

首次dp: dp[1] =true, wordDict 包含'A';

二次dp: dp[2] =true,

dp[1] =true, wordDict 包含'A';

三次dp: dp[3] =true,

dp[1] =true, wordDict 包含'AA';

...

最后一次dp: dp[12] =false,

dp[1]=truewordDict 不包含'AAleetcodeB';

dp[2]=truewordDict 不包含'AleetcodeB';

dp[3]=truewordDict 不包含'leetcodeB';

dp[7]=truewordDict 不包含'codeB';

dp[11]=truewordDict 不包含'B'

故,dp[12] =false.

java版本代码如下:

classSolution{

publicbooleanwordBreak(String s, List wordDict){

if(s ==null)returnfalse;

Set wordSet =newHashSet();

for(inti =; i

wordSet.add(wordDict.get(i));

}

boolean[] dp =newboolean[s.length() +1];

// 状态开始

dp[] =true;

// dp[i]表示能不能到达第i个字母的时候

for(inti =1; i

for(intj =; j

String current = s.substring(j, i);

if(dp[j] && wordSet.contains(current)) {

dp[i] =true;

break;

}

}

}

returndp[s.length()];

}

}

时间复杂度：O(n^2)。两层for循环。

空间复杂度: O(n)。dp数组长度是n。

DFS

动态规划和记忆化搜索都是很常用的解法，本题我们可以用一个数组记下位置i到字符串结束能不能够由wordDict组成。还是我们最开始的例子：

输入: s ="AAAleetcodeB", wordDict = ["leet","code","A","AA","AAA"]

首次for循环:'A'可以被 wordDict组成

'AA'可以被 wordDict组成

...

'AAAleetcodeB'不可以被 wordDict组成

这次深搜后记住：

从第一个字母'A'第二个字母'A', 第三个字母'A'... 开始的子串都不能由wordDict组成;

java代码：

publicclassSolution{

publicbooleanwordBreak(String s, List wordDict){

if(s ==null)returnfalse;

Set wordSet =newHashSet(wordDict);

// 记忆从i到字符串结束能不能搜索到.

Boolean[] memoToEndContain =newBoolean[s.length()];

returndfs(s,, wordSet, memoToEndContain);

}

publicbooleandfs(String s,

intstart,

Set wordSet,

Boolean[] memoToEndContain){

// 搜索到最后.

if(start == s.length()) {

returntrue;

}

// 之前已经搜索过.

if(memoToEndContain[start] !=null) {

returnmemoToEndContain[start];

}

for(intend = start +1; end

if(wordSet.contains(s.substring(start, end))

&& dfs(s, end, wordSet, memoToEndContain)) {

returnmemoToEndContain[start] =true;

}

}

memoToEndContain[start] =false;

returnmemoToEndContain[start];

}

}

时间复杂度：O(n^2)。搜索树的大小最多达到 n^2 。

空间复杂度: O(n)。深度优先二叉搜索树深度最多是n。

-END-