05 August 2008
字符串数组中的字符串任意多个连接起来后，没有重复字符的最长的结果
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private int max = 0;
public int maxLength(List<String> arr) {
dfs(arr, 0, "");
return max;
}
public void dfs(List<String> arr, int index, String concatenatStr) {
if (isUnique(concatenatStr)) max = Math.max(max, concatenatStr.length());
if (index == arr.size() || !isUnique(concatenatStr)) return;
for (int i = index; i < arr.size(); i++) {
dfs(arr, i + 1, concatenatStr + arr.get(i));
}
}
public boolean isUnique(String s) {
int[] alpha = new int[26];
for (int i = 0; i < s.length(); i++) alpha[s.charAt(i) - 'a']++;
for (int i = 0; i < alpha.length; i++) if (alpha[i] > 1) return false;
return true;
}
}