[LeetCode] 1286. Iterator for Combination #1286

grandyang · 2019-05-30T16:34:09Z

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.

这道题让设计一个 CombinationIterator 类，初始化时给一个有序的字符串，然后一个组合的长度，有两个成员函数，一个是 next() 函数，是返回下一个按字母顺序，且是给定长度的组合，另一个 hasNext() 函数用来判断是否还存在下一个组合。给的例子可以很好的帮助我们理解题意，比如给的字符串是 "abc"，返回组合的长度是2的话，则就是按照字母顺序来返回组合，"ab", "ac", "bc"。其实本质就是找出给定长度的所有组合，就拿给的例子 "abc" 来说吧，找出两个字母的组合，就是在三个字母中任意选两个，如果用1表示选择该字母，0表示不选的话，就有如下种情况：

a b c
0 0 0 -> ""
0 0 1 -> c
0 1 0 -> b
0 1 1 -> bc
1 0 0 -> a
1 0 1 -> ac
1 1 0 -> ab
1 1 1 -> abc

而每种情况正好对应一个二进制数，有三个字母的话，子集总个数为 2^3 = 8 个，每一种可以用一个二进制 mask 来表示，目标就是找出长度为2的组合。至于字母顺序不用太担心，将所有找出的组合放到一个 TreeSet 中，利用其自动排序的功能就行了。所以 mask 从1遍历到 2^n（这里的n为3），然后遍历给定字符串的长度，去看 mask 对应位上是1还是0，为1的话就将对应位的字母加到t中，最后看t的长度是多少，若是2的话，就加到 TreeSet 中。等将所有的长度为2的组合就找出来加到 TreeSet 中了之后，next 和 hasNext 函数就非常好实现了，用一个 iterator 就行了，next 就是看迭代器是否到末尾了，是的话返回空，否则返回当前指向到元素，并且迭代器后移一位。hasNext 就看迭代器是否到末尾了就行了，参见代码如下：

解法一：

class CombinationIterator {
public:
    CombinationIterator(string characters, int combinationLength) {
        st = generateAll(characters, combinationLength);
        cur = begin(st);
    }    
    string next() {
        return cur == end(st) ? "" : *cur++;
    }    
    bool hasNext() {
        return cur != end(st);
    }

private:
    set<string> st;
    set<string>::iterator cur;
    
    set<string> generateAll(string str, int len) {
        set<string> res;
        int n = 1 << str.size();
        for (int mask = 1; mask < n; ++mask) {
            string t = "";
            for (int i = 0; i < str.size(); ++i) {
                if (mask & (1 << i)) t += str[i];
            }
            if (t.size() == len) res.insert(t);
        }
        return res;
    }
};

我们也可以用迭代的方法来找出所有的组合，写法能稍微简洁一些，递归函数 generateAll 需要多加两个参数，start 和 res，分别是当前遍历到的位置，而当前组成的字符串。在递归函数中，若 len 为0了，则表示找到所求长度的组合，将其加入 TreeSet 中，否则就从 start 遍历到 n-len，然后调用递归函数，此时代入 len-1，i+1，和 res+str[i] 作为参数即可，参见代码如下：

解法二：

class CombinationIterator {
public:
    CombinationIterator(string characters, int combinationLength) {
        generateAll(characters, combinationLength, 0, "");
        cur = begin(st);
    }    
    string next() {
        return cur == end(st) ? "" : *cur++;
    }    
    bool hasNext() {
        return cur != end(st);
    }

private:
    set<string> st;
    set<string>::iterator cur;
    
    void generateAll(string str, int len, int start, string res) {
        if (len == 0) {
            st.insert(res);
            return;
        }
        for (int i = start; i <= (int)str.size() - len; ++i) {
            generateAll(str, len - 1, i + 1, res + str[i]);
        }
    }
};

Github 同步地址:

#1286

参考资料：

https://leetcode.com/problems/iterator-for-combination/

https://leetcode.com/problems/iterator-for-combination/discuss/451322/(JAVA)-Generate-Combinations

https://leetcode.com/problems/iterator-for-combination/discuss/451368/C%2B%2B-solution-with-multiple-pointers

https://leetcode.com/problems/iterator-for-combination/discuss/789164/C%2B%2B-Using-Bit-manipulation-or-Detail-Explain

LeetCode All in One 题目讲解汇总(持续更新中...)

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏