题目

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 of length combinationLength in lexicographical order.
  • A function hasNext() that returns True if and only if there exists a next combination.

Example:

  1. CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.
  3. iterator.next(); // returns "ab"
  4. iterator.hasNext(); // returns true
  5. iterator.next(); // returns "ac"
  6. iterator.hasNext(); // returns true
  7. iterator.next(); // returns "bc"
  8. iterator.hasNext(); // returns false

Constraints:

  • 1 <= combinationLength <= characters.length <= 15
  • There will be at most 10^4 function calls per test.
  • It’s guaranteed that all calls of the function next are valid.

题意

给定一个字符串s和一个整数k，从s中选出k个字符组成排列，按顺序求出每一个排列。

思路

维护一个长度为k的数组selected，selected[i]表示当前排列中第i个字符在s中的下标。显然，为了使一个排列合法，selected[i]不能超过一个特定的值(s.length-(selected.length-i))，不然s中剩余的字符个数不足以填充到k。如果selected[i]小于这个特定值，则只要将selected[i]指向下一个字符，并重置i之后所有的位置为其第一个合法位置，即可得到下一个排列；如果selected[i]等于这个特定值，则缩小i重复操作。

代码实现

Java

  1. class CombinationIterator {
  2.     private String s;
  3.     private int[] selected;
  4.     private boolean init;
  6.     public CombinationIterator(String characters, int combinationLength) {
  7.         s = characters;
  8.         selected = new int[combinationLength];
  9.         for (int i = 0; i < combinationLength; i++) {
  10.             selected[i] = i;
  11.         }
  12.         init = true;
  13.     }
  15.     public String next() {
  16.         if (init) {
  17.             init = false;
  18.             return generate();
  19.         }
  21.         for (int i = selected.length - 1; i >= 0; i--) {
  22.             int end = s.length() - (selected.length - i);
  23.             if (selected[i] < end) {
  24.                 selected[i]++;
  25.                 int j = 1;
  26.                 while (i + j < selected.length) {
  27.                     selected[i + j] = selected[i] + j;
  28.                     j++;
  29.                 }
  30.                 break;
  31.             }
  32.         }
  33.         return generate();
  34.     }
  36.     public boolean hasNext() {
  37.         return s.length() - selected[0] > selected.length;
  38.     }
  40.     private String generate() {
  41.         StringBuilder sb = new StringBuilder();
  42.         for (int i = 0; i < selected.length; i++) {
  43.             sb.append(s.charAt(selected[i]));
  44.         }
  45.         return sb.toString();
  46.     }
  47. }