leetcode 1286 字母组合迭代器

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

请你设计一个迭代器类，包括以下内容：

一个构造函数，输入参数包括：一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。 函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。 函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 True；否则，返回 False。

示例：

CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator

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

提示：

1 <= combinationLength <= characters.length <= 15
每组测试数据最多包含 10^4 次函数调用。
题目保证每次调用函数 next 时都存在下一个字母组合。

可以参考题解，这里的思路是设置一个等长的01序列，用于表示字母组合，最关键的是如何用01序列表示出组合，这里给出题解中的例子：

ab
ac
ad
bc
bd

1100
1010
1001
0110
0101
0011

二进制从大到小，只需要满足一定的1个数条件即可，所以，就从最大的2进制递减，判断1的个数，判断见下面的num1函数。设定一个标志位用于表示是否有下一个。

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.combinationLength = combinationLength
        self.pos = 2**len(characters) - 1
        for i in range(self.pos, 0, -1):
            if self.num1(i) == self.combinationLength:
                self.pos = i
                break
        self.N = True

    def next(self) -> str:
        result = ''.join([c for p, c in zip(
            bin(self.pos)[2:].zfill(len(self.characters)),
            self.characters) if p == '1'])
        self.N = False
        for i in range(self.pos - 1, 0, -1):
            if self.num1(i) == self.combinationLength:
                self.pos = i
                self.N = True
                break
        return result


    def hasNext(self) -> bool:
        return self.N
        
    def num1(self, num):
        count = 0
        while num:
            num = num & num - 1
            count += 1
        return count