解題說明
Iterator for Combination
題目描述: 設計一個 CombinationIterator 類別,接收一個由互不相同的小寫英文字母組成的排序字串 characters 和一個整數 combinationLength。實現 next() 回傳下一個長度為 combinationLength 的組合(按字典序),以及 hasNext() 判斷是否還有下一個組合。
解題思路: 使用索引陣列來追蹤當前組合中每個字元的位置。初始化時,索引設為 [0, 1, 2, ..., combinationLength-1]。每次呼叫 next() 時,先根據當前索引建構結果字串,然後將索引推進到下一個有效的組合。推進邏輯:從最右邊的索引開始,找到可以遞增的位置(即不會超出範圍),遞增後將其右邊的索引依次設置為連續值。
C++ 解法
複雜度分析
時間複雜度:next() 為 O(k),hasNext() 為 O(1)。其中 k 為 combinationLength
空間複雜度:O(k) — 儲存索引陣列
虛擬碼
1. Initialize: store characters string, set indices = [0, 1, ..., k-1], hasMore = true 2. next(): a. Build result string from chars[indices[0..k-1]] b. Find rightmost index i where indices[i] < n - k + i c. If no such i exists, set hasMore = false d. Otherwise, increment indices[i] and set indices[j] = indices[j-1] + 1 for j > i e. Return result 3. hasNext(): return hasMore
其他解法
方法二:預計算所有組合 在建構子中用回溯法預先產生所有組合並存入佇列。next() 直接從佇列取出。優點是 next() 為 O(1),缺點是初始化需要 O(C(n,k) × k) 的時間和空間,當 n 較大時可能浪費記憶體。
方法三:位元遮罩(Bitmask) 用一個整數的二進位表示來追蹤選擇了哪些字元。從 (1<<n)-1 開始往下遞減,找到恰好有 k 個 1 的數字即為有效組合。優點是概念簡潔,缺點是可能需要跳過許多無效的數字。
延伸思考
- 如果字元可以重複(允許重複組合),你會如何修改迭代器?
- 能否實現一個 prev() 方法,回到上一個組合?這對空間複雜度有什麼影響?
- 如果組合長度不固定,需要同時迭代所有可能長度的組合(按字典序),你會如何設計?