串联所有单词的子串，c++基础题

class Solution {
public:
unordered_map<string, int> words_mp;
int wsize;//单个word的长度
int wordssize;//word的总个数
bool ismatch(const string& s, int index, int num)//回溯匹配函数
{
if (num == wordssize)
{
return true;
}
if (index + wsize > s.size())
{
return false;
}
auto it = words_mp.find(s.substr(index, wsize));
if (it != words_mp.end())
{
if (it->second == 0)
{
return false;
}
--it->second;
if (ismatch(s, index + wsize, num + 1))
{
++it->second;
return true;
}
else
{
++it->second;
return false;
}
}
else
{
return false;
}
}
vector findSubstring(string s, vector& words) {
for (const string& word : words)
{
++words_mp[word];
}
wsize = words[0].size();
wordssize = words.size();
int ssize = s.size() - wsize + 1;
vector ans;
for (int i = 0; i < ssize; ++i)
{
if (ismatch(s, i, 0))
{
ans.push_back(i);
}
}
return ans;
}
};
这是力扣原题中的c++，秦淮孤道的回溯解法，第30道题，解法中c++模块第一个就是，来个认真负责的
问： --it->second;以及++it->second;作者的目的是对已经修改的哈希表进行复原，我看了好久都没有明白为什么要复原，谁能用简单易懂详细的语言解释为什么要复原，如果it->second指向了第一个元素，再减不会溢出吗，这时候计算机是怎么处理的
问：for (const string& word : words) { ++words_mp[word]; }这个哈希表++words_mp[word]; 这个什么意思呢，是将word依次放入哈希表吗，为什么不用put（word[i],i）,希望能详细讲解一下，++words_mp[word]; 难道不是words_mp[word]+1吗，为什么。key的值是自动赋予的吗
问： wsize = words[0].size();，这里为什么不考虑words[i]中不同的值得长度不一样，words[0]这里我感觉有错误啊，是我的错了吗，为什么不写成for（int i=0;i++;）{word[i].size();}呢，希望能认真解答一下
来个认真负责的大佬

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;


class Solution
{
public:
    unordered_map<string, int> words_mp;              // 记录单词可供匹配的数目，words中可能有重复的单词
    int wsize;                                        // 单个word的长度
    int wordssize;                                    // word的总个数

    // s: 字符串
    // index: 子串开始位置
    // num: 已经匹配单词的数目
    bool ismatch(const string &s, int index, int num) // 回溯匹配函数
    {
        if (num == wordssize) // 如果已经匹配单词数目等于words的单词个数，则匹配成功
        {
            return true;
        }
        if (index + wsize > s.size()) // 如果index+wsize大于s.size()，说明从index开始的子串不能匹配words中的任何单词（因为所有单词长度相等），则匹配失败
        {
            return false;
        }
        auto it = words_mp.find(s.substr(index, wsize)); // 在words_mp中查找从index开始长度为wsize的子串
        if (it != words_mp.end()) // 如果找到该子串
        {
            if (it->second == 0) // 但是如果该子串可供匹配数目为0，说明该单词在之前都已经匹配完了（words中单词可能有重复），则匹配失败
            {
                return false;
            }
            --it->second; // 否则，匹配该单词，让其可供匹配单词数目减1
            if (ismatch(s, index + wsize, num + 1)) // 递归匹配下一个字串，位置从index+wsize开始，已经匹配单词数目为num+1
            {
                ++it->second; // 恢复单词计数
                return true;
            }
            else
            {
                ++it->second; // 恢复单词计数
                return false;
            }
        }
        else // 如果没有找到该子串，则匹配失败
        {
            return false;
        }
    }

    vector findSubstring(string s, vector &words)
    {
        for (const string &word : words)
        {
            ++words_mp[word];      // 统计每个单词数目，注意words里可能有重复的单词
        }
        wsize = words[0].size();   // 题目规定了每个word的长度相等，wsize存储的是单词的长度
        wordssize = words.size();  // wordssize存储的是单词的个数
        int ssize = s.size() - wsize + 1;
        vector ans;
        for (int i = 0; i < ssize; ++i) // 依次对字符串s的每个位置进行匹配检查，由于words里所有单词长度相同，结束条件少一个单词的长度
        {
            if (ismatch(s, i, 0))  // 如果s中从i开始的字串匹配了words所有单词拼接，则存储该下标i到结果中
            {
                ans.push_back(i);
            }
        }
        return ans;  // 返回所有匹配的下标
    }
};

1.首先了解map映射表和itorator迭代器。
map::find()是头文件下的函数。此函数返回一个迭代器，该迭代器指向要搜索的给定键的元素。
此时的it就是迭代器了，it ->first是key，it->second 是value。
map类型是string，int，那此时的--it->second相当于把map的值做自减操作，这里也就是对value操作，复原是因为每次都用不能影响到下一次的回溯。
2.words_mp[word]相当于数组了，map是键值对，这个也就是word为key的value。++这个值就是自增。就是吧他给的所有单词全初始化到map中并且计数。
3.这个就是先定一个循环的范围，比如ab给的单词是a，那么就需要最少循环2次，也就是ab的长度减第一个单词的长度+1，初步判断循环次数。

进来学习一下

问： --it->second;以及++it->second;作者的目的是对已经修改的哈希表进行复原，我看了好久都没有明白为什么要复原，谁能用简单易懂详细的语言解释为什么要复原，如果it->second指向了第一个元素，再减不会溢出吗，这时候计算机是怎么处理的
it是unordered_set的迭代器,这个set的第二个元素指的是这个单词在words里面出现了多少次,--就是意味着，程序把这个单词用过一次，++再复原，它用的是深度搜索方式，也就是说通过递归，搜索一次后还要把现场复原。继续往下搜索。
比如从第一个单词搜索，那我把第一个单词出现的数量要减一，因为用过了一次
问：for (const string& word : words) { ++words_mp[word]; }这个哈希表++words_mp[word]; 这个什么意思呢，是将word依次放入哈希表吗，为什么不用put（word[i],i）,希望能详细讲解一下，++words_mp[word]; 难道不是words_mp[word]+1吗，为什么。key的值是自动赋予的吗
同一问。
问： wsize = words[0].size();，这里为什么不考虑words[i]中不同的值得长度不一样，words[0]这里我感觉有错误啊，是我的错了吗，为什么不写成for（int i=0;i++;）{word[i].size();}呢，希望能认真解答一下
你没有详细看题目，题目就是多个相同长度的单词，是否能拼接为字符串的字串。

来个认真负责的大佬

其实，你自己用深度搜索写个排列算法，这个题目很好界
比如1，2，3的全排列
1、先把1 取出来-》求2，3的全排列.
2、把2取出来-》求1，3的全排列
3、把3取出来-》求1，2全排列
上述每一步做完，都要把前面每一步的1，2，3恢复。