题大概是这样，一个INPUT STRING ARRAY1 比如CAT, DOG，一个INPUT STRING ARRAY 2， 比如GAT, DOC, CD, GOAT, BAD, COOL
要求第一个INPUT ARRAY的字母必须全部用，而且每个字母只能用一次，求其能组合成的INPUT STRING ARRAY2里的单词组合
比如上面这个例子，返回值会是{{GAT, DOC},{CD, GOAT}}
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=201395
My code:
private int[] charSet = new int[26];
private int charSum = 0;
public List<List<String>> wordSearchAnagram(List<String> input1, List<String> input2) {
for (String s : input1) {
for (char c : s.toCharArray()) {
charSet[c - 'a']++;
charSum++;
}
}
List<List<String>> ret = new ArrayList<List<String>>();
search(0, input2, new ArrayList<String>(), ret, 0);
return ret;
}
private void search(int begin, List<String> input2, List<String> group, List<List<String>> ret, int counter) {
if (counter > charSum) {
return;
}
else if (counter == charSum) {
int[] temp = Arrays.copyOf(charSet, 26);
for (String s : group) {
for (char curr : s.toCharArray()) {
temp[curr - 'a']--;
if (temp[curr - 'a'] < 0) {
return;
}
}
}
ret.add(new ArrayList<String>(group));
}
else {
for (int i = begin; i < input2.size(); i++) {
group.add(input2.get(i));
search(i + 1, input2, group, ret, counter + input2.get(i).length());
group.remove(group.size() - 1);
}
}
}
注意，如果 dictionary 里面的单词可以重复使用，那么，
search(i, ...) 而不是 search(i + 1, ...)
Anyway, Good luck, Richardo! -- 09/27/2016
