给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

 

 

思路：

看题目一眼  题意很明朗 颤颤巍巍的用暴力方法写了一遍 贴一下代码

public int maxProduct(String[] words) {
		int res = 0;
		for (int i = 0; i < words.length; i++) {
			String str1 = words[i];
			for (int j = 0; j < words.length; j++) {
				String str2 = words[j];
				if (str1 != str2 && !hasSameChar(str1, str2)) {
					res = Math.max(res, str1.length() * str2.length());
				}
			}

		}

		return res;
	}

	private boolean hasSameChar(String str1, String str2) {
		char[] arr2 = str2.toCharArray();
		for (int i = 0; i < arr2.length; i++) {
			char c = arr2[i];
			if (str1.contains(c + "")) {
				return true;
			}
		}
		return false;
	}

果然，超时了。。。

 

再想一想其他方法

 

考虑一下使用位运算

把每个字符串数组看成一个26大小的数组，小写字母a-z是26位，“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111， “wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000
这样两个进行与（&）  如果得到0则不含相同元素， 如果不为0则有相同元素。 

public int maxProduct(String[] words) {
		int len = words.length;
		if (len <= 1)
			return 0;
		int[] mask = new int[len];
		
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < words[i].length(); j++) {
				mask[i] |= 1 << (words[i].charAt(j) - 'a');
			}
		}
		int res = 0;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if ((mask[i] & mask[j]) == 0) {    //不含相同元素
					res = Math.max(res, words[i].length() * words[j].length());
				}
			}
		}
		return res;
	}