C ++中的组合迭代器

假设我们必须设计一个Iterator类,其中包含少量操作-

  • 定义一个构造函数,该构造函数将以不同的小写英文字母排序的字符串字符和一个数字CombineLength作为参数。

  • 定义一个函数next(),该函数将按字母顺序返回长度combinationLength的下一个组合。

  • 定义另一个函数hasNext(),当且仅当存在下一个组合时,该函数才返回True。

所以如果输入像-

CombinationIterator iterator = new CombinationIterator("xyz", 2);
iterator.next(); // returns "xy"
iterator.hasNext(); // returns true
iterator.next(); // returns "xz"
iterator.hasNext(); // returns true
iterator.next(); // returns "yz"
iterator.hasNext(); // returns false

为了解决这个问题,我们将遵循以下步骤-

  • 创建一个字符串数组梳,并索引idx

  • 定义一个方法makeCombs(),它将使用字符串s,整数变量l,一个临时字符串(最初为空)和一个start(初始为0)。其定义如下-

  • 如果temp的大小= l,则将temp插入梳子并返回

  • 因为我在范围内开始到s的大小

    • makeCombs(s,l,temp + s [i],i + 1)

  • printVector()方法将字符串数组作为输入,这将显示该数组的元素

  • 定义构造函数如下:它将使用字符串c和cl,

  • 调用makeCombs(c,cl),设置idx:= 0

  • next()方法将增加idx并返回comb [idx-1]

  • hasNext()如果idx与梳的大小不同,则该方法将返回true,否则返回false。

例子(C ++)

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class CombinationIterator {
public:
   vector <string> combs;
   int idx;
   void makeCombs(string s, int l, string temp ="", int start = 0){
      if(temp.size() == l){
         combs.push_back(temp);
         return;
      }
      for(int i = start; i < s.size(); i++){
         makeCombs(s, l, temp + s[i], i + 1);
      }
   }
   void printVector(vector <string> v){
      for(int i = 0; i < v.size(); i++){
         cout << v[i] << "\n";
      }
      cout << endl;
   }
   CombinationIterator(string c, int cl) {
      makeCombs(c, cl);
      idx = 0;
   }
   string next() {
      idx++;
      return combs[idx - 1];
   }
   bool hasNext() {
      return !(idx == combs.size());
   }
};
main(){
   CombinationIterator ob("xyz", 2);
   cout << (ob.next()) << endl;
   cout << (ob.hasNext()) << endl;
   cout << (ob.next()) << endl;
   cout << (ob.hasNext()) << endl;
   cout << (ob.next()) << endl;
   cout << (ob.hasNext()) << endl;
}

输入值

Initialize with “xyz” and 2, then call next() and hasNext() multiple times

输出结果

xy
1
xz
1
yz
0