完全背包的排列问题
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>(wordDict);
//字符串的长度为i 能凑成s为true，是dp[i]
//字符串从1开始计数，0代表空字符串?
boolean[] valid = new boolean[s.length() + 1];
valid[0] = true;
for(int i = 1;i<=s.length();i++){
for (int j = 0; j < i && !valid[i]; j++) {
if (set.contains(s.substring(j, i)) && valid[j]) {
valid[i] = true;
}
}
}
return valid[s.length()];
}
}