很经典的题目，标准的dfs。

树🌳的题很多都是明显的dfs，而list/string/array并不是那么明显，拼substring的dfs的题可以说是非常珍贵了。

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
class Solution {
    
    private int res = 0;
    
    public int maxLength(List<String> arr) {
        if (arr == null || arr.size() == 0) return 0;
        dfs(arr, "", 0);
        return res;
    }
    
    public void dfs(List<String> arr, String path, int index) {
        boolean unique = isUnique(path);
        // dfs: length now: unique or not
        if (unique) res = Math.max(res, path.length());
        // recursion ends;       not unique
        if (index == arr.size() || !unique) return ;
        
        for (int i = index; i < arr.size(); ++i) {
            // dfs: append next string to current path
            dfs(arr, path + arr.get(i), i + 1);
        }
        
        
    }
    
    public boolean isUnique(String s) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (set.contains(c)) return false;
            set.add(c);
        }
        return true;
    }
}

dfs内部, 开始部分:

  1. if(unique): 满足条件，更新res;
  2. index == arr.size() || !unique: 递归条件不满足, return;
  3. dfs部分的递归: path+arr.get(i): path增加; i+1: i也增加