Design an Iterator class, which has:<\/p>\n\n\n\n
characters<\/code> of sorted distinct<\/strong> lowercase English letters and a number combinationLength<\/code> as arguments.<\/li>- A function next()<\/em> that returns the next combination of length
combinationLength<\/code> in lexicographical order<\/strong>.<\/li>- A function hasNext()<\/em> that returns
True<\/code> if and only if there exists a next combination.<\/li><\/ul>\n\n\n\nExample:<\/strong><\/p>\n\n\n\nCombinationIterator iterator = new CombinationIterator(\"abc\", 2); \/\/ creates the iterator.\n\niterator.next(); \/\/ returns \"ab\"\niterator.hasNext(); \/\/ returns true\niterator.next(); \/\/ returns \"ac\"\niterator.hasNext(); \/\/ returns true\niterator.next(); \/\/ returns \"bc\"\niterator.hasNext(); \/\/ returns false\n<\/pre>\n\n\n\nConstraints:<\/strong><\/p>\n\n\n\n1 <= combinationLength <= characters.length <= 15<\/code><\/li>- There will be at most
10^4<\/code> function calls per test.<\/li>- It’s guaranteed that all calls of the function
next<\/code> are valid.<\/li><\/ul>\n\n\n\nSolution: Bitmask<\/strong><\/h2>\n\n\n\nUse a bitmask to represent the chars selected.
start with (2^n – 1), decrease the mask until there are c bit set.
stop when mask reach to 0.<\/p>\n\n\n\n
mask: 111 => abc
mask: 110 => ab
mask: 101 => ac
mask: 011 => bc
mask: 000 => “” Done<\/p>\n\n\n\n
Time complexity: O(2^n)
Space complexity: O(1)<\/p>\n\n\n\n
\nC++<\/h2>\n\n\n\nclass CombinationIterator {\npublic:\n CombinationIterator(string characters, int combinationLength): \n chars_(rbegin(characters), rend(characters)),\n length_(combinationLength),\n mask_((1 << characters.size()) - 1) {}\n\n string next() {\n hasNext(); \n string ans;\n for (int i = chars_.size() - 1; i >= 0 ; --i)\n if ((mask_ >> i) & 1)\n ans.push_back(chars_[i]);\n --mask_;\n return ans;\n }\n\n bool hasNext() {\n while (mask_ >= 0 && __builtin_popcount(mask_) != length_) --mask_;\n return mask_ > 0;\n }\nprivate:\n int mask_ = 0; \n const int length_;\n const string chars_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126],"tags":[122,33,177,4],"class_list":["post-7748","post","type-post","status-publish","format-standard","hentry","category-bit","tag-combination","tag-dfs","tag-medium","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7748","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7748"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7748\/revisions"}],"predecessor-version":[{"id":7750,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7748\/revisions\/7750"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7748"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7748"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}