题解 | #单词拆分(一)#
单词拆分(一)
http://www.nowcoder.com/practice/c0d32c1ce5744472a01b2351a2c2767f
题目描述：
给定一个字符串和一个字符串数组，判断是否存在将字符串任意划分后得到的子字符串都是字符串数组的子集
方法一：动态规划
-
首先，确定dp数组下标以及含义，dp[i]表示s[0,i]是否是字符串数组的子集。
-
确定递推公式，枚举结束位置end，在0到end之间枚举开始位置start,当s[0,start]是set的子集，如果s[start,end]也是set的子集,推出
-
从递推公式可以看出dp[j]是依赖于前面先推出的值，我们需要先初始化dp[0]为true,即空集为集合的子集。
- 确定遍历顺序，从上图可以看出遍历顺序是从左到右
function wordDiv( s , dic ) {
// write code here
var dp=[s.length+1];
var set=new Set(dic);
dp[0]=true;
for(let i=1;i<s.length+1;i++ ){
for(let j=0;j<i;j++){
if(dp[j]&&set.has(s.substring(j,i))){
dp[i]=true;
break;
}
}
}
return dp[s.length];
}
module.exports = {
wordDiv : wordDiv
};
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串一维数组
* @return bool布尔型
*/
public boolean wordDiv (String s, String[] dic) {
// write code here
HashSet<String> set = new HashSet<>();
for(String word: dic){
set.add(word);//先移除重复字符串
}
boolean[] dp = new boolean[s.length() + 1];//dp[i]表示s字符串中前i个字符是不是set的子集
dp[0] = true;//空串可以被词表中的词表示
for(int end = 1; end <= s.length(); end++){
for(int start = 0; start < end; start++){
if(dp[start] && set.contains(s.substring(start, end))){
//s[0:start]是set的子集，s[start:end]也是set的子集，所以s[0:end]是set的子集，dp[end]=true
dp[end] = true;
break;
}
}
}
return dp[s.length()];
}
}
复杂度：
- 时间复杂度：,双重循环。
- 空间复杂度：,dp数组和集合set均占用空间
查看10道真题和解析
