139 Word Break【逐一对比vs.多种 分割 组合】

片面思考的思路：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {//字符串和对应的字典，如果s种可以用空格分隔出一个或多个字典里的词就返回true//核心：按照字典里的词对s断句，对s遍历，如何判断s种有多余的字母是字典中不包含的？//细节：字典里的词会被多次使用，且不按顺序出//在这道题中，哈希表是怎么使用的？是存储字典中出现的单词个数？还是存储s中的单词出现的位置？//如何确定单词范围？对dic也是一个一个比较吗？比较后怎么锁定s中的位置？//单词范围由wordDic[i].size()确定，通过substr(pos,len)确定子串中的位置，哈希表用于存储开始位置和单词长度//是哪个循环套哪个循环？//因为一个字典会在s中多次出现且s的长度最大值才300所以Dic中嵌套s//如何让s遍历的时候跳过已经判断出的范围？或者说如何判定s没有被排除完？//s.replace(pos,len,'0')那这样就不需要哈希表了啊，直接最后遍历一遍是否全为0就好了//unordered_map<int,int> StartAndLength;int index = 0;for(int i = 0 ; i < wordDict.size();i++){int len = wordDict[i].size();int index = 0;//每次都从头开始遍历while(index < s.size()){if(s[index] == wordDict[i][0] && s.substr(index,len) == wordDict[i]){//StartAndLength[index] = len;s.replace(index,len,string(len,' '));index+=len;}else{index++;}}}for(char ch : s){if(ch != ' '){return false;}}return true;}
};

分析思路过程：

按照字典里的词对s断句，对s遍历，如何判断s种有多余的字母是字典中不包含的？
细节：字典里的词会被多次使用，且不按顺序出
在这道题中，哈希表是怎么使用的？ 是存储字典中出现的单词个数？还是存储s中的单词出现的位置？-----》都是对中间态的记录，没有考虑哈希表的快速查找
如何确定单词范围？ 对dic也是一个一个比较吗？比较后怎么锁定s中的位置？
单词范围由wordDic[i].size()确定，通过substr(pos,len)确定子串中的位置，哈希表用于存储开始位置和单词长度-------》没有考虑多种组合的情况
//是哪个循环套哪个循环？
//因为一个字典会在s中多次出现且s的长度最大值才300所以Dic中嵌套s
如何让s遍历的时候跳过已经判断出的范围？或者说如何判定s没有被排除完？
完全遍历一遍，所以主体还是对s的遍历

重新思考这道题目

按照难度来说，中等题也不太可能使用逐一对比+替换就能解决这个问题；
按照题型来说，这道题肯定需要用哈希表来解决
重新思考这道题，复盘哪些问题需要继续去思考的：

• 在这道题中，哈希表是怎么使用的？
• 如何确定单词范围？
• 如何判断s中有多余的字母是字典中不包含的？---->这个是多种组合？

第一个问题： 哈希表可以完成字典的快速查找unordered_set，记录中间状态 unordered_map；
如果是前一种，也就是将wordDict变了一下，用于快速查找s子串种是否是字典中的单词hash.find(s.substr(pos,len)) != hash.end()就是查到了，这段子串是存在于hash中的。
【这种方式特别适合需要频繁查找字典的情况，因为 unordered_set 的查找操作具有平均 O(1) 的时间复杂度，非常高效。】
后一种的话，就是用哈希表记录检查过的字符串段，用于判断s已经被分割的字段，但这个不适合多种组合的情况，类似于逐一对比，认准一个死理不改变，所以还是使用字典的快速查找。
第二个问题： 单词范围一种是遍历，确定s中的开始位置使用while和Dict中的单词逐一对比，已经被pass了；另一种是动态规划，动态规划尤其适用于需要检查多个可能分割点并且组合的情况，如字符串分割、路径问题等。
第三个问题： 实际上是回答怎么判定s是否可以被Dict中的单词们分割，结合第二个问题，使用动态规划划分单词范围，其中的dp[i]数组表示的是s中前i个字符是否可以被完全分割，如果在最终的dp数组中s.size()位置标记为false则表示无法分割。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {//动态规划//要做的事情是确定s中前i位是否可以被分割 dp[i]vector<bool> dp(s.size()+1,false);unordered_set<string> wordSet(wordDict.begin() , wordDict.end());//初始条件dp[0] = true;dp[0] = true;//遍历string s找合适的切割组合for(int i = 1 ; i <= s.size() ; i++){//判定是否可以被分割for(int j = 0 ; j < i ; j++){//判定条件，关系式：wordSet.find(s.substr(j , i-j)) != wordSet.end()if(dp[j] && wordSet.find(s.substr(j , i-j)) != wordSet.end()){//可以被分割dp[i] = true;break;}}}return dp[s.size()];}
};

review 467 Unique Substrings in Wraparound String

class Solution {
public:int findSubstringInWraproundString(string s) {//不同的非空的子串数目 不同+非空怎么判定-->记录数组dp 仅记录以26字母为结尾的//要找的是 且是不同的 存在于base中的子串 所以判定dp[i]为以i = ch - 'a'为索引，以ch为结尾的最长子串vector<int> dp(26,0);int maxLen = 0;//base的判定前者-后者为1 或者前者为z后者为a,记录长度for(int i = 0 ; i < s.size() ; i++){char ch = s[i];if(i>0 && (s[i] - s[i-1] == 1 || (s[i-1] == 'z' && s[i] == 'a'))){maxLen++;}else{//初始条件maxLen = 1;}dp[ch-'a'] = std::max(maxLen,dp[ch-'a']);}int ans = 0;for(int len : dp){ans += len;}return ans;}
};