Сложность: medium
Создайте класс CombinationIterator:
CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.
Пример:
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
👨💻 Алгоритм:
1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.
2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.
3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.
😎 Решение:
class CombinationIterator {
var combinations: [String]
init(_ characters: String, _ combinationLength: Int) {
combinations = []
let n = characters.count
let k = combinationLength
for bitmask in 0..<(1 << n) {
if bitmask.nonzeroBitCount == k {
var curr = ""
for j in 0..<n {
if bitmask & (1 << (n - j - 1)) != 0 {
curr.append(characters[characters.index(characters.startIndex, offsetBy: j)])
}
}
combinations.append(curr)
}
}
}
func next() -> String {
return combinations.removeLast()
}
func hasNext() -> Bool {
return !combinations.isEmpty
}
}Ставь 👍 и забирай 📚 Базу знаний