1. 题目链接
2. 题目简介
给定一个非空字符串 S 和一个包含非空单词的列表 wordDict，判定 S 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: S = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
3. 题目分析
- 题目可简化为：
给你一些字符串，这些字符串可不可以拼成目标S并且字符串可以重复使用 - 可见该问题为一个
完全背包问题，对于完全背包来说，我们有一个模板：外层为我们的目标S，内层为我们的选择的东西 - 我们来看这道题的转移方程，我们定义dp数组：
boolean[] dp = new boolean[s.length() + 1];，dp[i]代表 0 ~ i 的字符串可以被拼接，我们想一想，假如dp[i]的字符串可以被拼接，那我们dp[i + 1, len]也能被拼接的话，是不是代表该 S 字符串拼接成功。 - 所以，我们的转移方程为：
dp[i] = dp[j] && check[j, i-1]
if(dp[j] && check(j, i)){ dp[i] = true; break; }
4. 题目代码
class Solution { public boolean wordBreak(String s, List<String> wordDict) { int len = s.length(); boolean[] dp = new boolean[len + 1]; // 去重 可哈希搜索 Set<String> set = new HashSet(wordDict); if(len == 1){ return set.contains(s); } // 0这个位置肯定是可以被搜索到的 dp[0] = true; for(int i = 1; i <= len; i++){ for(int j = 0; j < i; j++){ if(dp[j] && set.contains(s.substring(j, i))){ dp[i] = true; break; } } } return dp[len]; } }
