代码随想录 139.单词拆分

思路一、回溯。1.本题看上去和回溯算法分割回文串很像就是枚举字符串的所有分割情况。上题是枚举字符串分割后的所有子串判断是否回文。本题是枚举分割所有字符串判断是否在字典里出现过。结果会超时。2.记忆化搜索递归的过程中有很多重复计算可以用数组保存一下递归过程中重复计算的结果也就是记忆化搜索。使用memory数组保存每次计算的以startIndex为起始的计算结果如果memory[startIndex]里已经被赋值了直接用memory[startIndex]里的结果。可以AC。class Solution { private: bool backtracking (const string s, const unordered_setstring wordSet, vectorbool memory, int startIndex) { if (startIndex s.size()) { return true; } // 如果memory[startIndex]不是初始值了直接使用memory[startIndex]的结果 if (!memory[startIndex]) return memory[startIndex]; for (int i startIndex; i s.size(); i) { string word s.substr(startIndex, i - startIndex 1); if (wordSet.find(word) ! wordSet.end() backtracking(s, wordSet, memory, i 1)) { return true; } } memory[startIndex] false; // 记录以startIndex开始的子串是不可以被拆分的 return false; } public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring wordSet(wordDict.begin(), wordDict.end()); vectorbool memory(s.size(), 1); // -1 表示初始化状态 return backtracking(s, wordSet, memory, 0); } };二、背包问题。单词就是物品字符串s就是背包单词能否组成字符串s就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词因此是完全背包问题。动规五部曲1.确定dp数组及其下标的含义dp[i]表示字符串长度为i时若为true则能拆分为一个或多个在字典中出现的单词。2.确定递推公式1如果确定dp[j]为true且[ji]这个区间的子串出现在字典里那么dp[i]一定为truej i。2所以递推公式是if([j,i]这个区间的子串出现在字典里dp[j] true)那么dp[i] true。3.dp数组如何初始化1从递推公式中可以看出dp[i]的状态依靠dp[j]是否为true所以dp[0]就是递推的根基。dp[0]一定要为true否则递推下去后面都是false了。2dp[0]的意义dp[0]表示如果字符串为空的话说明出现在字典里题目已经说明非空字符串s因此不会出现i为0的情况dp[0]初始为true就是为了推导公式。3下标非0的dp[i]初始化为false只要没有被覆盖说明是不可拆分为一个或多个在字典中出现的单词。4.确定遍历顺序1本题是完全背包问题。如果求组合数就是外层for循环遍历物品内层for循环遍历背包。如果求排列数就是外层for循环遍历背包内层for循环遍历物品。2本题实际上是求排列数以s applepenapple, wordDict [apple, pen] 为例。apple, pen 是物品要求物品的组合一定是 apple pen apple 才能组成 applepenapple。apple apple pen 或者 pen apple apple 是不可以的那么我们就是强调物品之间顺序。3所以本题要先遍历背包再遍历物品。5.举例推导dp[i]。以输入: s leetcode, wordDict [leet, code]为例dp状态如下图dp[s.size()]就是最终结果附代码class Solution { public boolean wordBreak(String s, ListString wordDict) { // 将List转换为HashSet单次查找时间复杂度从O(n)优化为O(1) HashSetString set new HashSet(wordDict); // boolean[]数组的初始值默认都是false boolean[] valid new boolean[s.length() 1]; // 前0个字符可以用字典中的单词拼出只做初始化用 valid[0] true; for(int i 1;i s.length();i){ // 一旦确定dp[i]为true就不再继续尝试其他j值 // 即通过短路优化节省不必要的计算 for(int j 0;j i !valid[i];j){ // substring是前闭后开区间 // 但是这里的i表示的是长度而不是索引前i个长度的字符的索引正好是[0,i) if(set.contains(s.substring(j,i)) valid[j]){ valid[i] true; } } } return valid[s.length()]; } }ACM模式import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取字符串 s String s scanner.nextLine(); // 读取单词个数 int n scanner.nextInt(); scanner.nextLine(); // 消耗换行符否则下面的第一次读取会读取到空串 // 读取 wordDict ListString wordDict new ArrayList(); for (int i 0; i n; i) { wordDict.add(scanner.nextLine()); } // 调用解法 Solution solution new Solution(); boolean result solution.wordBreak(s, wordDict); // 输出结果 System.out.println(result); scanner.close(); } } class Solution { public boolean wordBreak(String s, ListString wordDict) { // 将List转换为HashSet单次查找时间复杂度从O(n)优化为O(1) HashSetString set new HashSet(wordDict); // boolean[]数组的初始值默认都是false boolean[] valid new boolean[s.length() 1]; valid[0] true; for (int i 1; i s.length(); i) { // 一旦确定dp[i]为true就不再继续尝试其他j值 // 即通过短路优化节省不必要的计算 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()]; } }