导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-318.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.

翻译

给出一个字符串数组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。
没有无相同字母的单词。

对于每个单词,设一个26位的int,位操作,记录其字母出现情况。
判断两个单词是否有相同字母时,只要对其对应的int做与操作,如果结果为0,则无相同字母。
时间复杂度O(n):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public int maxProduct(String[] words) {
// 记录每个单词中字母情况的int数组,每个元素为26位int
int[] letters = new int[words.length];
for (int i = 0; i < words.length; i++) {
int letter = 0;
for (char c : words[i].toCharArray())
letter |= 1 << (c - 'a');
letters[i] = letter;
}

int res = 0;
for (int i = 0; i < words.length; i++) {
for (int j = i + 1; j < words.length; j++) {
if ((letters[i] & letters[j]) == 0) {
int len = words[i].length() * words[j].length();
res = len > res ? len : res;
}
}
}

return res;
}
}

参考:
https://segmentfault.com/a/1190000004186943