描述
给定字符串 s 和单词字典 dict，判断是否可以利用字典 dict 中的出现的单词拼接出 s，其中字典 dict 中的单词可以重复使用。
因为我们已经使用了更强大的数据，所以普通的DFS方法无法解决此题
s.length<=1e5
dict.size<=1e5
样例 1：
输入：
s = "lintcode"
dict = ["lint", "code"]输出：
true解释：
lintcode可以分成lint和code。
样例 2：
输入：
s = "a"
dict = ["a"]输出：
true解释：
a在dict中
思路:判断dict是否可以拼出目标字符串s.首先判断使用哪种算法
简单来说 常用的求方案总数 最值 可行性大多数用动态规划 即不是具体的方案
也可以细分通过最优子结构和重叠子问题判断
最优子结构（切最后一段）
把字符串 s[0..i) 能否拆分，拆到“最后一段”来想：
存在某个切分点 j<i，若
前缀
s[0..j)可拆（这是一个更小的同类问题），并且最后一段
s[j..i)在词典里，
则s[0..i)也可拆。
这直接给出状态与转移：dp[i] = OR_{j<i}( dp[j] && inDict(s[j..i)) ) OR即逻辑或
等价文字写法就是存在某个 j（0 ≤ j < i），使得前缀 s[0..j) 可拆且最后一段 s[j..i) 在字典里，那么 dp[i] 为真
重叠子问题
不同的 i 会反复查询相同的前缀可行性，比如 dp[10]、dp[11] 都会用到 dp[7]、dp[8] 等。DP一次算好可以重复利用
知道用动态规划后那么下面就是动态规划的四要素
//状态 dp[i]
//状态转移方程 递推一下
判断“前 i 个字符可拼”就看“它的最后一刀切在哪个 j”。
“左边可拼 + 右边是词” ⇒ 整体可拼。
所以在代码里对所有 j 做
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true; break;
}
其中状态转移方程为:dp[i]=dp[j]&&wordSet.contains(s.substring(j,i));
//初始化dp[0]=true;
//边界条件s.length()<Set.size()&&s.length()>=0
代码如下:
public class Solution {
/**
* @param s: A string
* @param wordSet: A dictionary of words dict
* @return: A boolean
*/
public boolean wordBreak(String s, Set<String> wordSet) {
// 健壮性
if (s == null || wordSet == null) return false;
int n=s.length();
boolean dp[]=new boolean[n+1];//易错点1 容易少写一个 为n因为dp[0]占据了一位 dp[i] 表示：前 i 个字符 即
//s = "leet"，n = 4
//我们需要 dp[0], dp[1], dp[2], dp[3], dp[4] 共 5 个状态：
//dp[0]=空串，dp[4]=整串结果 →自然是 n+1 即dp[]数组是状态表示 表示长度为 n 的串,有 //n+1 个切分点（含头尾）
dp[0]=true;
int maxWordLength=0;//最长单词长度
int minWordLength=Integer.MAX_VALUE;//最短单词长度
//maxWordLength：保证不检查比任何词都长的片段 → 收紧 j 的起点。
//minWordLength：保证不检查比任何词都短的片段 → 可以提前从 i=minWordLength 开跑，//并收紧 j 的终点 剪枝截取片段是从j至i
//分别统计单词的最长长度和最短长度
for(String str:wordSet)
{
int currentWordLength=str.length();
if (currentWordLength == 0)
{
continue;
}
if(maxWordLength<currentWordLength)
{
maxWordLength=currentWordLength;
}
if(minWordLength>currentWordLength)
{
minWordLength=currentWordLength;
}
}
for(int i=minWordLength;i<=n;i++)
{
int jStart = Math.max(0, i - maxWordLength);
for (int j = jStart; j < i; j++)
{
if(dp[j]&&wordSet.contains(s.substring(j,i)))
{
dp[i] = true;
break;
}
}
}
return dp[n];
}
}