318. 最大单词长度乘积

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 342 阅读时长 ≈ 1 分钟

考点

  • 状态压缩

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
	private:
		unordered_map<int, int> m;
	public:
		int maxProduct(vector<string>& words) {
			for (string &word : words) {
				int hsh = 0;
				for (char &chr : word) {
					hsh |= 1 << (chr - 'a');
				}
				m[hsh] = max(m[hsh], (int)word.length());
			}
			int ans = 0;
			for (auto it_1 = m.begin(); it_1 != m.end(); it_1++) {
				for (auto it_2 = next(it_1); it_2 != m.end(); it_2++) {
					if ((it_1->first & it_2->first) == 0) {
						ans = max(ans, it_1->second * it_2->second);
					}
				}
			}
			return ans;
		}
};

时间复杂度：\(O\left( \max \left( \sum\nolimits_{0\leqslant i\leqslant n-1}^{}{words\left[ i \right]}.length,n^2 \right) \right)\)，\(n\)为\(words\)数组长度

其中构造哈希表的时间复杂度为\(O\left( \sum\nolimits_{0\leqslant i\leqslant n-1}^{}{words\left[ i \right]}.length \right)\)，计算最大乘积的时间复杂度为\(O\left( n^2 \right)\)

空间复杂度：\(O\left( n \right)\)

思路

按照传统的办法，比较两个字符串的组成需要新建哈希表并遍历，耗时\(O\left( n \right)\)

若按照题意，所有字符串两两比较，时间复杂度高达\(O\left( n^3 \right)\)，是绝对不可取的

题目限制了字符串只含有小写字母，可以使用一个int的低26位来记录字符串中的字母组成

该int可以作为哈希表的键，值则是对应字符串的长度；字母的组成肯定有雷同，所以只记录组成相同里长度最大的

最后再双重遍历哈希表，寻找长度乘积最大的即可