leetcode Maximum Product of Word Lengths

leetcode Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] Return 16 The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"] Return 4 The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"] Return 0 No such pair of words.

Follow up: Could you do better than O(_n_2), where n is the number of words?

题目地址: leetcode Maximum Product of Word Lengths

题意：给定一个字符串数组，求它们中，元素各不相同的字符串长度乘积最大值。

如样例1中，abcw 和 xtfn 成绩为4*4 =16 （元素互不相同）而abcw 和 abcdef为0，因为有相同的元素

思路：

方法一

直接看看每个字符串都包括了哪个字符，然后一一枚举是否有交集：

有交集，则乘积为0
无交集，乘积为 words[i].length() * words[j].length()

于是写出如下代码

C++

class Solution {
public:
	int maxProduct(vector<string>& words) {
		int n = words.size();
		vector<vector<int> > elements(n, vector<int>(26, 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < words[i].length(); j++)
				elements[i][words[i][j] - 'a'] ++;
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				bool flag = true;
				for (int k = 0; k < 26; k++) {
					if (elements[i][k] != 0 && elements[j][k] != 0) {
						flag = false;
						break;
					}
				}
				if (flag && words[i].length() * words[j].length()  > ans)
					ans = words[i].length() * words[j].length();
			}
		}
		return ans;
	}
};

方法二

其实因为全部都是小写的字母，用int 就可以存储每一位的信息。这就是位运算

elements[i] = 1 << (words[i][j] - 'a'); //把words[i][j] 在26字母中的出现的次序变为1
elements[i] & elements[j] // 判断是否有交集只需要两个数按位与（AND）运算即可

C++

class Solution {
public:
	int maxProduct(vector<string>& words) {
		int n = words.size();
		vector<int> elements(n, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < words[i].length(); j++)
				elements[i] |= 1 << (words[i][j] - 'a');
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (!(elements[i] & elements[j]) && words[i].length() * words[j].length()  > ans)
					ans = words[i].length() * words[j].length();
			}
		}
		return ans;
	}
};

Java

public class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] elements = new int[n];
        for (int i=0;i<n;i++){
            for(int j=0;j<words[i].length();j++){
                elements[i] = 1 << (words[i].charAt(j) - 'a');
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((elements[i] & elements[j]) == 0)
                    ans = Math.max(ans,words[i].length() * words[j].length());
            }
        }
        return ans;
    }
}

Python

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        n = len(words)
        elements = [0] * n
        for i, s in enumerate(words):
            for c in s:
                elements[i] = 1 << (ord(c) - 97)

        ans = 0
        for i in xrange(n):
            for j in xrange(i + 1, n):
                if not (elements[i] & elements[j]):
                    ans = max(ans, len(words[i]) * len(words[j]))
        return ans