0318. Maximum Product of Word Lengths

---

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Constraints:

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists only of lowercase English letters.

---

解法1

用int二位数组memo来保存字符串数组的信息, 其中子数组长度为26,表示26个小写英文字母.

java

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length, res = 0;
        // 二位数组, 保存words中每一个字符串中含有哪些字符
        int[][] memo = new int[n][26];
        for (int i = 0; i < n; i++) {
            int[] row = new int[26];
            // 只需要保存是否含有的信息就可以
            for (char c : words[i].toCharArray())
                row[c - 'a'] = 1;
            memo[i] = row;
        }

        for (int i = 0; i < n; i++) {
            int len1 = words[i].length();
            for (int j = i + 1; j < n; j++) {
                if (!hasSameChar(memo, i, j))
                    res = Math.max(res, len1 * words[j].length());
            }
        }
        return res;
    }

    // 判断words[i]和words[j]是否含有相同字符
    private boolean hasSameChar(int[][] memo, int i, int j) {
        int[] arr1 = memo[i], arr2 = memo[j];
        for (int k = 0; k < 26; k++)
            if (arr1[k] == 1 && arr2[k] == 1)
                return true;
        return false;
    }
}

C#

public class Solution {
    public int MaxProduct(string[] words) {
        var n = words.Length;
        var res = 0;
        // 二位数组, 保存words中每一个字符串中含有哪些字符
        var memo = new int[n,26];
        for (var i = 0; i < n; i++) 
            // 只需要保存是否含有的信息就可以
            foreach(var c in words[i].ToCharArray())
                memo[i, c - 'a'] = 1;

        for (var i = 0; i < n; i++) {
            var len1 = words[i].Length;
            for (var j = i + 1; j < n; j++) {
                if (!HasSameChar(memo, i, j))
                    res = Math.Max(res, len1 * words[j].Length);
            }
        }
        return res;
    }

    // 判断words[i]和words[j]是否含有相同字符
    private bool HasSameChar(int[,] memo, int i, int j) {
        for (var k = 0; k < 26; k++)
            if (memo[i, k] == 1 && memo[j, k] == 1)
                return true;
        return false;
    }
}

---

解法2

解法1用int[26]来保存字符串是否含有某个字符. 其实可以用int的二进制形式来保存.

java

class Solution {
    public int maxProduct(String[] words) {
        
        int n = words.length, res = 0;
        int[] memo = new int[n];
        for (int i = 0; i < n; i++) {
            int info = 0;
            // info的二进制形式,对应位置的1表示含有该字符
            // 是倒序保存
            for (char c : words[i].toCharArray())
                info = (info | (1<<(c - 'a')));
            memo[i] = info;
        }

        for (int i = 0; i < n; i++) {
            int len1 = words[i].length();
            for (int j = i + 1; j < n; j++) {
                if (!hasSameChar(memo, i, j))
                    res = Math.max(res, len1 * words[j].length());
            }
        }
        return res;
    }

    // 判断words[i]和words[j]是否含有相同字符
    private boolean hasSameChar(int[] memo, int i, int j) {
        return (memo[i]&memo[j]) > 0;
    }
}

C#

public class Solution {
    public int MaxProduct(String[] words) {
        var n = words.Length;
        var res = 0;
        var memo = new int[n];
        for (var i = 0; i < n; i++) {
            var info = 0;
            // info的二进制形式,对应位置的1表示含有该字符
            // 是倒序保存
            foreach (var c in words[i].ToCharArray())
                info = (info | (1<<(c - 'a')));
            memo[i] = info;
        }

        for (var i = 0; i < n; i++) {
            var len1 = words[i].Length;
            for (var j = i + 1; j < n; j++) {
                if (!HasSameChar(memo, i, j))
                    res = Math.Max(res, len1 * words[j].Length);
            }
        }
        return res;
    }

    // 判断words[i]和words[j]是否含有相同字符
    private bool HasSameChar(int[] memo, int i, int j) {
        return (memo[i] & memo[j]) > 0;
    }
}