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
class Solution {
    private int max;

    public int maxLength(List<String> arr) {
        int[] charOccur = new int[arr.size()];
        for (int i = 0; i < charOccur.length; i++) {
            charOccur[i] = getCharOccur(arr.get(i));
        }
        backtrack(arr, charOccur, 0, 0);
        return max;
    }

    private void backtrack(List<String> arr, int[] charOccur, int currOccur, int pos) {
        if (pos == arr.size()) {
            max = Math.max(max, getOnes(currOccur));
            return;
        }

        if (charOccur[pos] != -1 && (currOccur & charOccur[pos]) == 0) {
            backtrack(arr, charOccur, currOccur | charOccur[pos], pos + 1);
        }
        backtrack(arr, charOccur, currOccur, pos + 1);
    }

    private int getCharOccur(String s) {
        int ans = 0;
        for (char letter : s.toCharArray()) {
            int targetPos = (1 << (int) (letter - 'a'));
            if ((ans & targetPos) != 0) {
                ans = -1;
                break;
            }
            ans |= targetPos;
        }
        return ans;
    }

    private int getOnes(int num) {
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += (num & 1);
            num >>= 1;
        }
        return ans;
    }
}

backtrack, 用一个int来记录每一个string中出现了哪些char, 如果某个char出现多次, 则该标记为-1. 最后用getOnes来查一查currOccur中有几个1即可.

时间复杂度: O(2^n)
空间复杂度: O(n)