https://leetcode.cn/problems/word-break/description/
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 思路较为巧妙,和传统背包定义不同
// f[i]表示长度为i的字符串能否被wordDict里的单词凑成
// 状态转义方程也和传统背包不同,需要从题意出发来进行推导
// 若有j<=i,且 s[j~i]这个子串是 存在于wordDict中的,且f[j]=true
// 意味着可以由f[j]推导出f[i],即f[i]= f[j] && check(s[j~i])
// 那么答案就是f[s.length()]
// 由于求的不是组合而是排列,因此需要先背包再物品
// 初值:为了方便进行推导,定义f[0]表示空串,为true,f[1]才表示凑成第一个字符的选法,这里f[0]不会影响答案,只是便于计算推导
// 相当于把s当做背包,s的子串当做物品,判断wrodDict中是否存在,存在即可以凑出来s
Map<String,Boolean> map = new HashMap<>();
for(String str:wordDict)map.put(str,true);
int N = 310;
boolean[] f=new boolean[N];
f[0]=true;
for(int i=1;i<=s.length();i++)
{
for(int j=0;j<i;j++) // 子串
{
String substr=s.substring(j,i);
Boolean flag=map.get(substr);
if(f[j]==true && flag!=null && flag==true)
f[i]=true;
}
}
return f[s.length()];
}
}
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 另一种f定义
// 这类集合中选元素,且是排列问题的,统一可以当做爬楼梯模型来做
// 如,f[i]表示能否爬到第i阶楼梯,或者说能否构字符串s
// 以最后一步从哪爬取的来划分子集,且能爬上来的一定是wordDict的谋个元素
// 即求f[i]的话,是从小于i的楼层爬上来的
// 能够一步爬上来意味着j~i之间这个子串存在于wordDict中
// f[i]=f[j] && j~i这个子串存在于wordDict中
// f[0]表示第0层楼,一定能爬上,为true
Map<String,Boolean> map = new HashMap<>();
for(String str:wordDict)map.put(str,true);
int N = 310;
boolean[] f=new boolean[N];
f[0]=true;
for(int i=1;i<=s.length();i++)
{
for(int j=0;j<i;j++) // 子串
{
String substr=s.substring(j,i);
Boolean flag=map.get(substr);
if(f[j]==true && flag!=null && flag==true)
f[i]=true;
}
}
return f[s.length()];
}
}
标签:String,int,boolean,拆分,wordDict,new,139,true,leetcode From: https://www.cnblogs.com/lxl-233/p/18397208