Iterator for Combination

 

Iterator for Combination

Design an Iterator class, which has:

• A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• A function next() that returns the next combination of length combinationLength in lexicographical order.
• A function hasNext() that returns True if and only if there exists a next combination.

 

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

 

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• There will be at most 10^4 function calls per test.
• It's guaranteed that all calls of the function next are valid.

class CombinationIterator {
private:
    string st;
    int val;
    vector<string> v;
public:
    void helper(int start,int k,string perm)
    {
        if(perm.size()==k)
        {
            v.push_back(perm);
            return ;
        }
        for(int i=start;i<st.size();++i)
        {
            perm.push_back(st[i]);
            helper(i+1,k,perm);
            perm.pop_back();
        }
    }
    CombinationIterator(string s, int l)
    {
       st=s;
        helper(0,l,"");
        val=0;
    }
   
    string next() {
        return v[val++];
    }
   
    bool hasNext() {
        if(val<v.size())
        return true;
        else
        return false;
    }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */