算法训练营day46

一、单词拆分

元素无重可复选

1. base case i==s.length return true，遍历到了最后,
   1. 因为i+len = s.length，len初始值为1，那么i+1 = s.length，那么i = s.lenth -1 也就是最后一个字符位置
2. dp(s,i)函数定义：返回 s[i…] 是否能够被拼出
3. 判断字符串S的前缀[0,k]是否存在于WordDict，存在就递归dp(s, i+len)

class Solution {// 用哈希集合方便快速判断是否存在HashSet<String> wordDict;// 备忘录，-1 代表未计算，0 代表无法凑出，1 代表可以凑出int[] memo;// 主函数public boolean wordBreak(String s, List<String> wordDict) {// 转化为哈希集合，快速判断元素是否存在this.wordDict = new HashSet<>(wordDict);// 备忘录初始化为 -1this.memo = new int[s.length()];Arrays.fill(memo, -1);return dp(s, 0);}// 定义：s[i..] 是否能够被拼出boolean dp(String s, int i) {// base caseif (i == s.length()) {return true;}// 防止冗余计算if (memo[i] != -1) {return memo[i] == 0 ? false : true;}// 遍历 s[i..] 的所有前缀for (int len = 1; i + len <= s.length(); len++) {// 看看哪些前缀存在 wordDict 中String prefix = s.substring(i, i + len);if (wordDict.contains(prefix)) {// 找到一个单词匹配 s[i..i+len)// 只要 s[i+len..] 可以被拼出，s[i..] 就能被拼出boolean subProblem = dp(s, i + len);if (subProblem == true) {memo[i] = 1;return true;}}}// s[i..] 无法被拼出memo[i] = 0;return false;}
}

二、单词拆分2

class Solution {HashSet<String> wordDict;// 备忘录List<String>[] memo;public List<String> wordBreak(String s, List<String> wordDict) {this.wordDict = new HashSet<>(wordDict);memo = new List[s.length()];return dp(s, 0);}// 定义：返回用 wordDict 构成 s[i..] 的所有可能List<String> dp(String s, int i) {List<String> res = new LinkedList<>();if (i == s.length()) {res.add("");return res;}// 防止冗余计算if (memo[i] != null) {return memo[i];}// 遍历 s[i..] 的所有前缀for (int len = 1; i + len <= s.length(); len++) {// 看看哪些前缀存在 wordDict 中String prefix = s.substring(i, i + len);if (wordDict.contains(prefix)) {// 找到一个单词匹配 s[i..i+len)List<String> subProblem = dp(s, i + len);// 构成 s[i+len..] 的所有组合加上 prefix // 就是构成构成 s[i] 的所有组合for (String sub : subProblem) {if (sub.isEmpty()) {// 防止多余的空格res.add(prefix);} else {res.add(prefix + " " + sub);}}}}// 存入备忘录memo[i] = res;return res;}
}