0%

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++

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
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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

请我喝杯咖啡吧~