c++ - 对于具有重复字符的字符串，字符串的排列失败

Question

我试图了解回溯是如何工作的。我正在研究字符串的排列。

class Solution {
public:
    void permute(string s,int count[], string res, int level, vector<string> &perS)
    {
        if( level == s.size())
        {
            //cout<<res<<endl;
            perS.push_back(res);
            return;
        }
        int i;
        for(i=0; i<s.size(); i++)
        {
            if(count[i]==0)
            {
                continue;
            }
            res += s[i];
            count[i]--;
            permute(s, count, res, level+1, perS);
            count[i]++;
            //this line is problem I think?? how to handle if s1 contains duplicates??
            res.erase(res.end()-1);
        }
        
    }
    
    bool checkInclusion(string s1, string s2) {
        map<char, int> mp;
        for(int i=0; i<s1.size(); i++)
        {
            mp[s1[i]]++; 
        }
        int *count = new int[mp.size()];
        set<char> us;
        //to generate the count array of all the characters
        for(int i=0; i<s1.size(); i++)
        {
            us.insert(s1[i]);
        }
        auto it = us.begin();
        for(int i=0; i<mp.size(); i++)
        {
            count[i] = mp[*it++]++;
        }
        
        string res;
        vector<string> perS;
        permute(s1, count, res, 0, perS);
        
        //check if s2 contains in pers;
        
        for(string x:perS)
        {
            if(s2.find(x)!=string::npos)
                return true;
        }
        return false;
    }
};

上面的代码在我将 s1 作为“helo”传递时有效，但如果它有重复项，则会给出 stackoverflow 错误。“你好”。

我试图理解的算法非常简单。我们从字符串中选择一个字符并遍历其他字符。一旦我们到达终点，我们就会回溯并检查其他选项。

我试过但无法理解为什么它因字符串重复而失败。 https://www.youtube.com/watch?v=nYFd7VHKyWQ&t=1346s 我正在尝试上述网址中解释的相同算法，但我正在尝试用 cpp 语言对其进行编码。

我非常感谢您对此的任何意见。这是我的第一个问题，请原谅我的任何错误。它将帮助我可视化回溯问题的递归流程。

标签： c++stringalgorithmbacktrackingrecursive-datastructures