LeetCode 1286.字母组合迭代器
原题链接:字母组合迭代器

1. 需要了解的知识点

又是一道全排列回溯问题。。。
全排列模板(回溯)

dfs()
{
    if()                     //出口
    {
        return ;
    }
    for(int i=0;i<n;i++)    //列举所有情况
    {
        if(!pd[i])
        {
            pd[i]=1;
            dfs();      
            pd[i]=0;        //回溯
        }
    }
}

相关视频链接:【算法】dfs刷题实战1

2. 难点:

字典序返回长度为 combinationLength 的下一个字母组合。

3. 思路

在创建CombinationIterator对象的同时,可以把字符串characters中所有长度为 combinationLength的字母组合都放到一个容器里,然后next()和hasNext()直接调用容器里的元素进行判断就ok了

4. 代码注释

变量定义的解释

vector<string> vec:储存所有字母组合的容器

int bean:vec中需要调用的next()的下标的位置

自定义函数

void dfs(const string characters,int last,const int& combinationLength,vector<string>&vec,string temp )

递归回溯将所有字母组合按顺序压入vec中(不想用太多参数,可以适量的定义全局变量)

const string characters:   题目给的字符串”abc“
int last:          上一个字母的下标
const int& combinationLengt: 每个字母组合的长度
vector<string>& vec:        目标容器
string temp:        临时字符串用来存储单个字母组合

  class CombinationIterator {
private:
    vector<string> vec;
    int bean;
public:
    void dfs(const string characters,int last,const int& combinationLength,vector<string>&vec,string temp )
    {
        if (temp.size() >= combinationLength)     //出口
        {
            vec.push_back(temp);                                 /*单个字母组合压入字母组合容器中*/
            return;
        }
        for (int i = last; i < characters.size(); i++)          /*全排列*/
        {
            temp.push_back(characters[i]);      
            dfs(characters, i+1, combinationLength, vec, temp); /*注意last的值*/
            temp.pop_back();                                    /*回溯*/
        }
    }

    CombinationIterator(string characters, int combinationLength) {
        /*构造函数内初始化所有变量*/
        string temp;
        bean = 0;
        dfs(characters,0, combinationLength, vec, temp);        /*初始化vec*/
    }
    string next() {    
        string str=*(vec.begin()+bean);                          /*vec的字母组合是按顺序的所以从第一个迭代器往下移动就得到下一个字母组合*/
        bean++;                                                  /*每移动一次加一*/
        return str;
    }

    bool hasNext() {
        if (vec.size() - bean >= 1) 
            return true;
            return false;
    }

};

5. 总结反思

没使用一个标记数组回溯,因为已经定义了一个last记录上一个下标的位置,不可能出现相同的排列,起到了去重的效果。

测试代码

int main()
{
    CombinationIterator* iterator = new CombinationIterator("abcdfghigkl", 8); 
    for (auto i : iterator->vec)
    {
        for (auto k : i)
        {
            cout << k << " ";
        }
        cout << endl;
    }
    return 0;
}

测试图片
图片名称