《剑指 Offer》专项突破版 - 面试题 5 : 单词长度的最大乘积（C++ 实现）

目录

前言

方法一

方法二

---

?

---

前言

题目链接：318. 最大单词长度乘积 - 力扣（LeetCode）

题目：

输入一个字符串数组 words，请计算不包含相同字符的两个字符串 words[i] 和 words[j] 的长度乘积的最大值。如果所有字符串都包含至少一个相同的字符，那么返回 0。假设字符串中只包含英文小写字母。例如，输入的字符串数组 words 为 ["abcw", "foo", "bar", "fxyz", "abcdef"]，数组中的字符串 "foo" 与 "bar" 没有相同的字符，它们的长度的乘积为 9；"abcw" 和 "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(vector<string>& 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(vector<string>& words) {
 ? ? ? ?int length = words.size();
 ? ? ? ?vector<vector<bool>> flags(length, vector<bool>(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(vector<string>& words) {
 ? ? ? ?int length = words.size();
 ? ? ? ?vector<int> 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 次位运算，因此方法二的时间效率更高。