面试算法5：单词长度的最大乘积

题目

输入一个字符串数组words，请计算不包含相同字符的两个字符串words[i]和words[j]的长度乘积的最大值。如果所有字符串都包含至少一个相同字符，那么返回0。假设字符串中只包含英文小写字母。例如，输入的字符串数组words为[“abcw”，“foo”，“bar”，“fxyz”，“abcdef”]，数组中的字符串"bar"与"foo"没有相同的字符，它们长度的乘积为9。"abcw"与"fxyz"也没有相同的字符，它们长度的乘积为16，这是该数组不包含相同字符的一对字符串的长度乘积的最大值。

分析1

解决这个问题的关键在于如何判断两个字符串str1和str2中没有相同的字符。一个直观的想法是基于字符串str1中的每个字符ch，扫描字符串str2判断字符ch是否出现在str2中。如果两个字符串的长度分别为p和q，那么这种蛮力法的时间复杂度是O（pq）。
也可以用哈希表来优化时间效率。对于每个字符串，可以用一个哈希表记录出现在该字符串中的所有字符。在判断两个字符串str1和str2中是否有相同的字符时，只需要从’a’到’z’判断某个字符是否在两个字符串对应的哈希表中都出现了。在哈希表中查找的时间复杂度是O（1）。这个题目假设所有字符都是英文小写字母，只有26个可能的字符，因此最多只需要在每个字符串对应的哈希表中查询26次就能判断两个字符串是否包含相同的字符。26是一个常数，因此可以认为应用哈希表后判断两个字符串是否包含相同的字符的时间复杂度是O（1）。
由于这个题目只需要考虑26个英文小写字母，因此可以用一个长度为26的布尔型数组来模拟哈希表。数组下标为0的值表示字符’a’是否出现，下标为1的值表示字符’b’是否出现，其余以此类推。

解1

public class Test {
    public static void main(String[] args) {
        String[] nums = {"abcw","foo","bar","fxyz","abcdef"};
        int result = maxProduct(nums);
        System.out.println(result);
    }

    public static int maxProduct(String[] words) {
        boolean[][] flags = new boolean[words.length][26];
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                flags[i][c - 'a'] = true;
            }
        }
        int result = 0;
        for (int i = 0; i < words.length; i++) {// words[i]
            for (int j = i + 1; j < words.length; j++) {// words[j]
                int k = 0;
                for (; k < 26; k++) {
                    if (flags[i][k] && flags[j][k]) {
                        break;
                    }
                }
                if (k == 26) {// words[i]和words[j]没有相同的字符
                    int prod = words[i].length() * words[j].length();
                    result = Math.max(result, prod);
                }
            }
        }
        return result;
    }
}
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

分析2

前面的解法是用一个长度为26的布尔型数组记录字符串中出现的字符。布尔值只有两种可能，即true或false。这与二进制有些类似，在二进制中数字的每个数位要么是0要么是1。因此，可以将长度为26的布尔型数组用26个二进制的数位代替，二进制的0对应布尔值false，而1对应true。

解2

public class Test {
    public static void main(String[] args) {
        String[] nums = {"abcw", "foo", "bar", "fxyz", "abcdef"};
        int result = maxProduct(nums);
        System.out.println(result);
    }

    public static int maxProduct(String[] words) {
        int[] flags = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char ch : words[i].toCharArray()) {
                flags[i] |= 1 << (ch - 'a');
            }
        }

        int result = 0;
        for (int i = 0; i < words.length; i++) {// words[i]
            for (int j = i + 1; j < words.length; j++) {// words[j]
                if ((flags[i] & flags[j]) == 0) {
                    int prod = words[i].length() * words[j].length();
                    result = Math.max(result, prod);
                }
            }
        }

        return result;
    }
}
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