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();
 */

1286 - Iterator for Combination

1286. Iterator for Combination (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1286. Iterator for Combination (Medium)

Solution 1.

All Problems

All Solutions