Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1286.html

1286. Iterator for Combination (Medium)

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.

Related Topics:
Backtracking, Design

Solution 1.

  • class CombinationIterator {
        private int curr;
        private int size;
        private char[] cs;
    
        public CombinationIterator(String characters, int combinationLength) {
            int n = characters.length();
            curr = (1 << n) - 1;
            size = combinationLength;
            cs = new char[n];
            for (int i = 0; i < n; ++i) {
                cs[i] = characters.charAt(n - i - 1);
            }
        }
    
        public String next() {
            while (curr >= 0 && Integer.bitCount(curr) != size) {
                --curr;
            }
            StringBuilder ans = new StringBuilder();
            for (int i = 0; i < cs.length; ++i) {
                if (((curr >> i) & 1) == 1) {
                    ans.append(cs[i]);
                }
            }
            --curr;
            return ans.reverse().toString();
        }
    
        public boolean hasNext() {
            while (curr >= 0 && Integer.bitCount(curr) != size) {
                --curr;
            }
            return curr >= 0;
        }
    }
    
    /**
     * 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:
        int size;
        string cs;
        int curr;
    
        CombinationIterator(string characters, int combinationLength) {
            int n = characters.size();
            curr = (1 << n) - 1;
            reverse(characters.begin(), characters.end());
            cs = characters;
            size = combinationLength;
        }
    
        string next() {
            while (curr >= 0 && __builtin_popcount(curr) != size) --curr;
            string ans;
            for (int i = 0; i < cs.size(); ++i) {
                if ((curr >> i) & 1) {
                    ans += cs[i];
                }
            }
            reverse(ans.begin(), ans.end());
            --curr;
            return ans;
        }
    
        bool hasNext() {
            while (curr >= 0 && __builtin_popcount(curr) != size) --curr;
            return curr >= 0;
        }
    };
    
    /**
     * 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):
            self.curr = (1 << len(characters)) - 1
            self.size = combinationLength
            self.cs = characters[::-1]
    
        def next(self) -> str:
            while self.curr >= 0 and self.curr.bit_count() != self.size:
                self.curr -= 1
            ans = []
            for i in range(len(self.cs)):
                if (self.curr >> i) & 1:
                    ans.append(self.cs[i])
            self.curr -= 1
            return ''.join(ans[::-1])
    
        def hasNext(self) -> bool:
            while self.curr >= 0 and self.curr.bit_count() != self.size:
                self.curr -= 1
            return self.curr >= 0
    
    
    # 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 {
    	curr int
    	size int
    	cs   []byte
    }
    
    func Constructor(characters string, combinationLength int) CombinationIterator {
    	n := len(characters)
    	curr := (1 << n) - 1
    	size := combinationLength
    	cs := make([]byte, n)
    	for i := range characters {
    		cs[n-i-1] = characters[i]
    	}
    	return CombinationIterator{curr, size, cs}
    }
    
    func (this *CombinationIterator) Next() string {
    	for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size {
    		this.curr--
    	}
    	ans := []byte{}
    	for i := range this.cs {
    		if (this.curr >> i & 1) == 1 {
    			ans = append(ans, this.cs[i])
    		}
    	}
    	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
    		ans[i], ans[j] = ans[j], ans[i]
    	}
    	this.curr--
    	return string(ans)
    }
    
    func (this *CombinationIterator) HasNext() bool {
    	for this.curr >= 0 && bits.OnesCount(uint(this.curr)) != this.size {
    		this.curr--
    	}
    	return this.curr >= 0
    }
    
    /**
     * 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