05 August 2008
检查一个string的的给定长度的combinations是否还有是谁这些个设计
逆序检查 顺序推进
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class CombinationIterator {
private char[] arr;
private int k;
private int[] last;
private char[] next;
public CombinationIterator(String characters, int combinationLength) {
arr = characters.toCharArray();
k = combinationLength;
last = new int[k];
next = new char[k];
}
public String next() {
// 首次
if (next[0] < 'a') {
for (int i = 0; i < k; i++)
next[i] = arr[last[i] = i];
return new String(next);
}
// 往后，delta 表示当前 last[i] 应该与最后相隔多少，可转为 k 表示
for (int i = k - 1, delta = 1; i >= 0; i--, delta++) {
// 逆序检查
if (last[i] + delta < arr.length) {
// 找到可升位字母
next[i] = arr[last[i] = last[i] + 1];
// 顺序推进，按 arr 顺序重新分配
for (int j = i + 1; j < k; j++)
next[j] = arr[last[j] = last[j - 1] + 1];
return new String(next);
}
}
return "-1";
}
public boolean hasNext() {
// 首字母升到头了
return last[0] < arr.length - k;
}
}
/**
* Your CombinationIterator object will be instantiated and called as such:
* CombinationIterator obj = new CombinationIterator(characters, combinationLength);
* String param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/