西安企业免费建站,wordpress所有文章页面,建站源码程序,微信如何建设网站目录
前言
方法一
方法二 前言
题目链接#xff1a;318. 最大单词长度乘积 - 力扣#xff08;LeetCode#xff09;
题目#xff1a;
输入一个字符串数组 words#xff0c;请计算不包含相同字符的两个字符串 words[i] 和 words[j] 的长度乘积的最大值。如果所有字符串…目录
前言
方法一
方法二 前言
题目链接318. 最大单词长度乘积 - 力扣LeetCode
题目
输入一个字符串数组 words请计算不包含相同字符的两个字符串 words[i] 和 words[j] 的长度乘积的最大值。如果所有字符串都包含至少一个相同的字符那么返回 0。假设字符串中只包含英文小写字母。例如输入的字符串数组 words 为 [abcw, foo, bar, fxyz, abcdef]数组中的字符串 foo 与 bar 没有相同的字符它们的长度的乘积为 9abcw 和 fxyz 也没有相同的字符它们长度的乘积为 16这是该数组中不包含相同字符的一对字符串的长度乘积的最大值。
分析
解决这个问题的关键在于如何判断两个字符串 str1 和 str2 中有没有相同的字符。一个直观的想法是基于字符串 str1 中的每个字符 ch扫描字符串 str2 判断字符串 ch 是否出现在 str2 中。如果两个字符串的长度分别为 p 和 q那么这种蛮力法的时间复杂度是 O(pq)。 方法一
可以用哈希表来优化时间效率。对于每个字符串可以用一个哈希表记录出现在该字符串中的所有字符。在判断两个字符串是否有相同的字符时只需要从 a 到 z 判断某个字符是否在两个字符串对应的哈希表中都出现了。在哈希表中查找的时间复杂度是 O(1)。这个题目假设所有字符都是英文小写字母只有 26 个可能的字符因此最多只需要在每个字符串对应的哈希表中查询 26 次就能判断两个字符串是否包含相同的字符。26 是一个常数因此可以认为应用哈希表判断两个字符是否具有相同的字符的时间复杂度是 O(1)。
由于这个题目只需要考虑 26 个英文小写字母因此可以用一个长度为 26 的布尔型数组来模拟哈希表。数组下标为 0 的值表示字符 a 是否出现下标为 1 的值表示字符 b 是否出现其余依次类推。
写法一
class Solution {
public:int maxProduct(vectorstring words) {int length words.size();bool** flags new bool*[length];for (int i 0; i length; i){flags[i] new bool[26];for (int j 0; j 26; j){flags[i][j] false;}}
for (int i 0; i length; i){for (char ch : words[i]){flags[i][ch - a] true;}}
int result 0;for (int i 0; i length; i){for (int j i 1; j length; j){int k 0;for (; k 26; k){if (flags[i][k] flags[j][k])break;}
if (k 26){int product words[i].size() * words[j].size();if (product result)result product;}}}
for (int i 0; i length; i){delete[] flags[i];}delete[] flags;
return result;}
};
写法二
class Solution {
public:int maxProduct(vectorstring words) {int length words.size();vectorvectorbool flags(length, vectorbool(26, false));for (int i 0; i length; i){for (char ch : words[i]){flags[i][ch - a] true;}}
int result 0;for (int i 0; i length; i){for (int j i 1; j length; j){int k 0;for (; k 26; k){if (flags[i][k] flags[j][k])break;}
if (k 26){int product words[i].size() * words[j].size();if (product result)result product;}}}
return result;}
}; 方法二
方法一是用一个长度为 26 的布尔型数组记录字符串中出现的字符。布尔值只有两种可能即 true 或 false。这与二进制有些类似在二进制中数字的每个数位要么是 0 要么是 1。因此可以将长度为 26 的布尔型数组用 26 个二进制的数位代替二进制的 0 对应布尔值 false而 1 对应 true。
C 中 int 型整数的二进制形式有 32 位但只需要 26 位就能表示一个字符串中出现的字符因此可以用一个 int 型整数记录某个字符串中出现的字符。如果字符串中包含 a那么整数最右边的数位为 1如果字符串中包含 b那么整数的倒数第 2 位为 1其余依次类推。这样做的好处是能更快地判断两个字符串是否包含相同的字符。如果两个字符串中包含相同的字符那么它们对应的整数相同的某个数位都为 1两个整数的与运算将不会为 0如果两个字符串没有相同的字符那么它们对应的整数的与运算的结果等于 0。
class Solution {
public:int maxProduct(vectorstring words) {int length words.size();vectorint flags(length, 0);for (int i 0; i length; i){for (char ch : words[i]){flags[i] | 1 (ch - a);}}
int result 0;for (int i 0; i length; i){for (int j i 1; j length; j){if ((flags[i] flags[j]) 0){int product words[i].size() * words[j].size();if (product result)result product;}}}return result;}
}; 注意方法一和方法二的时间复杂度是同一个量级的但是方法一在判断两个字符串是否包含相同的字符时可能需要 26 次布尔运算而方法二只需要 1 次位运算因此方法二的时间效率更高。
