题目描述
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 10^4 calls will be made to next and hasNext.
- It’s guaranteed that all calls of the function next are valid.
题目分析
按照题意，我们需要给出字符串s和指定组合长度l这2个条件下的迭代器实现
分析题目，其本质是要按照某种规律每次选取出l个字符，保证每次选出的字符构成的字符串相比于前一个，都是符合字典序的
同时，题目给出了几个重点条件：
- 字符串中的字符都是唯一的，不存在重复
- 字符串长度不会超过15
这里我们不妨将原字符串看做一个二进制位，初始状态下，前l个位置为1，其余都为0；这样，只要我们不断的对这个二进制位加1，当新的数字中1的数量等于l时，我们也就找到了下一个符合字典序的字符串组合
综上，代码如下:
示例代码
type CombinationIterator struct {
s string // 原字符串
len int // 组合长度
mask int // next组合的bit-mask
}
func Constructor(characters string, combinationLength int) CombinationIterator {
mask := 0
// 初始化mask，从最高位开始，前combinationLength个位置为1
for i := 0; i < combinationLength; i++ {
mask |= 1 << (len(characters) - 1 - i)
}
return CombinationIterator{
s: characters,
len: combinationLength,
mask: mask,
}
}
func (this *CombinationIterator) Next() string {
cur := this.mask
ans := []byte{}
start := 1 << (len(this.s) - 1)
i := 0
for start > 0 {
// 不断找出当前bit位为1的，对应bit-mask表示的字符串
if cur&start > 0 {
ans = append(ans, this.s[i])
}
i++
start = start >> 1
}
// 查找下一个mask，具有相同1的个数
for this.mask > 0 {
this.mask--
if this.countOnes(this.mask) == this.len {
break
}
}
return string(ans)
}
func (this *CombinationIterator) HasNext() bool {
// 若mask已为0，说明已经全部迭代完毕
return this.mask > 0
}
// 统计n的二进制中1的个数
func (this *CombinationIterator) countOnes(n int) int {
count := 0
for n > 0 {
n &= n - 1
count++
}
return count
}