Welcome to Subscribe On Youtube

1286. Iterator for Combination

Description

Design the CombinationIterator class:

  • CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
  • next() Returns the next combination of length combinationLength in lexicographical order.
  • hasNext() Returns true if and only if there exists a next combination.

 

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

 

Constraints:

  • 1 <= combinationLength <= characters.length <= 15
  • All the characters of characters are unique.
  • At most 104 calls will be made to next and hasNext.
  • It is guaranteed that all calls of the function next are valid.

Solutions

  • class CombinationIterator {
        private int n;
        private int combinationLength;
        private String characters;
        private StringBuilder t = new StringBuilder();
        private List<String> cs = new ArrayList<>();
        private int idx = 0;
    
        public CombinationIterator(String characters, int combinationLength) {
            n = characters.length();
            this.combinationLength = combinationLength;
            this.characters = characters;
            dfs(0);
        }
    
        public String next() {
            return cs.get(idx++);
        }
    
        public boolean hasNext() {
            return idx < cs.size();
        }
    
        private void dfs(int i) {
            if (t.length() == combinationLength) {
                cs.add(t.toString());
                return;
            }
            if (i == n) {
                return;
            }
            t.append(characters.charAt(i));
            dfs(i + 1);
            t.deleteCharAt(t.length() - 1);
            dfs(i + 1);
        }
    }
    
    /**
     * Your CombinationIterator object will be instantiated and called as such:
     * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
     * String param_1 = obj.next();
     * boolean param_2 = obj.hasNext();
     */
    
  • class CombinationIterator {
    public:
        string characters;
        vector<string> cs;
        int idx;
        int n;
        int combinationLength;
        string t;
    
        CombinationIterator(string characters, int combinationLength) {
            idx = 0;
            n = characters.size();
            this->characters = characters;
            this->combinationLength = combinationLength;
            dfs(0);
        }
    
        string next() {
            return cs[idx++];
        }
    
        bool hasNext() {
            return idx < cs.size();
        }
    
        void dfs(int i) {
            if (t.size() == combinationLength) {
                cs.push_back(t);
                return;
            }
            if (i == n) return;
            t.push_back(characters[i]);
            dfs(i + 1);
            t.pop_back();
            dfs(i + 1);
        }
    };
    
    /**
     * 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();
     */
    
  • class CombinationIterator:
        def __init__(self, characters: str, combinationLength: int):
            def dfs(i):
                if len(t) == combinationLength:
                    cs.append(''.join(t))
                    return
                if i == n:
                    return
                t.append(characters[i])
                dfs(i + 1)
                t.pop()
                dfs(i + 1)
    
            cs = []
            n = len(characters)
            t = []
            dfs(0)
            self.cs = cs
            self.idx = 0
    
        def next(self) -> str:
            ans = self.cs[self.idx]
            self.idx += 1
            return ans
    
        def hasNext(self) -> bool:
            return self.idx < len(self.cs)
    
    
    # Your CombinationIterator object will be instantiated and called as such:
    # obj = CombinationIterator(characters, combinationLength)
    # param_1 = obj.next()
    # param_2 = obj.hasNext()
    
    
  • type CombinationIterator struct {
    	cs  []string
    	idx int
    }
    
    func Constructor(characters string, combinationLength int) CombinationIterator {
    	t := []byte{}
    	n := len(characters)
    	cs := []string{}
    	var dfs func(int)
    	dfs = func(i int) {
    		if len(t) == combinationLength {
    			cs = append(cs, string(t))
    			return
    		}
    		if i == n {
    			return
    		}
    		t = append(t, characters[i])
    		dfs(i + 1)
    		t = t[:len(t)-1]
    		dfs(i + 1)
    	}
    	dfs(0)
    	return CombinationIterator{cs, 0}
    }
    
    func (this *CombinationIterator) Next() string {
    	ans := this.cs[this.idx]
    	this.idx++
    	return ans
    }
    
    func (this *CombinationIterator) HasNext() bool {
    	return this.idx < len(this.cs)
    }
    
    /**
     * Your CombinationIterator object will be instantiated and called as such:
     * obj := Constructor(characters, combinationLength);
     * param_1 := obj.Next();
     * param_2 := obj.HasNext();
     */
    

All Problems

All Solutions