?LeetCode刷題實(shí)戰(zhàn)318：最大單詞長(zhǎng)度乘積
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.
示例
示例 1:
輸入: ["abcw","baz","foo","bar","xtfn","abcdef"]
輸出: 16
解釋: 這兩個(gè)單詞為 "abcw", "xtfn"。
示例 2:
輸入: ["a","ab","abc","d","cd","bcd","abcd"]
輸出: 4
解釋: 這兩個(gè)單詞為 "ab", "cd"。
示例 3:
輸入: ["a","aa","aaa","aaaa"]
輸出: 0
解釋: 不存在這樣的兩個(gè)單詞。
解題
class Solution {
public:
int maxProduct(vector<string>& words) {
int result = 0;
int wordsSize = words.size();
//対第一個(gè)字符串窮舉
for (int nowIndex = 0; nowIndex < wordsSize; ++nowIndex){
//標(biāo)記第一個(gè)字符串各個(gè)字符出現(xiàn)
map<char, bool> firstMap;
for (auto ch : words[nowIndex]){
firstMap[ch] = true;
}
//窮舉第二個(gè)字符串
for (int afterIndex = nowIndex + 1; afterIndex < wordsSize; ++afterIndex){
int afterWordSize = words[afterIndex].size(), tempIndex = 0;
//判讀第一個(gè)、第二個(gè)字符串是否存在相同的字符
for (; tempIndex < afterWordSize; ++tempIndex){
if (firstMap[words[afterIndex][tempIndex]]){
break;
}
}
//如果不存在相同的字符
if (afterWordSize == tempIndex){
result = max(int(afterWordSize * words[nowIndex].size()), result);//更新結(jié)果
}
}
}
return result;
}
};
class Solution {
public:
int maxProduct(vector<string>& words) {
int result = 0;
int wordsSize = words.size();
vector<int> wordToInt(wordsSize, 0);//wordToInt[i]表示words[i]按照字母分別占據(jù)以為得到的int數(shù)據(jù)
//対第一個(gè)字符串窮舉
for (int nowIndex = 0; nowIndex < wordsSize; ++nowIndex){
//將第一個(gè)字符串按照字符占據(jù)位，計(jì)算為int
for (auto ch : words[nowIndex]){
wordToInt[nowIndex] |= (1 << (ch - 'a'));
}
//窮舉第二個(gè)字符串
for (int afterIndex = 0; afterIndex < nowIndex; ++afterIndex){
//如果不存在相同的字符
if ((wordToInt[nowIndex] & wordToInt[afterIndex]) == 0){
result = max(result, int(words[nowIndex].size() * words[afterIndex].size()));
}
}
}
return result;
}
};