C C++算法题解LeetCode1408数组中的字符串匹配

问题描述

给定字符串数组 words，在其中找到两个不同的单词，使得它们的长度之和最长。可以假设 words 中至少存在两个单词。

返回两个单词长度之和的最大值。

解题思路

方法一：暴力枚举

我们可以将字符串数组中的字符串两两组合，计算它们的长度之和并更新最大值，最后返回最大值即可。

时间复杂度：$O(n^2k)$，其中 $n$ 是字符串数组中字符串的个数，$k$ 是字符串的平均长度。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (check(words[i], words[j])) {
                    ans = max(ans, int(words[i].size() * words[j].size()));
                }
            }
        }
        return ans;
    }

    bool check(string s1, string s2) {
        vector<int> cnt(26);
        for (char c : s1) cnt[c - 'a']++;
        for (char c : s2) {
            if (cnt[c - 'a']) return false;
        }
        return true;
    }
};

方法二：位运算

观察题目给出的数据范围，发现单词的小写字母只有 $26$ 种，可以使用一个 $32$ 位的整数来记录一个单词中出现的字母。

我们可以先将字符串数组中的单词转换为对应的整数，然后再将整数两两做与运算，结果为 $0$ 的两个整数所对应的单词就是符合条件的两个单词。

时间复杂度：$O(n^2+\frac{n^2k⋅k}{32})$，其中 $n$ 是字符串数组中字符串的个数，$k$ 是字符串的平均长度。

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size(), ans = 0;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            for (char c : words[i]) {
                nums[i] |= 1 << (c - 'a');
            }
            for (int j = 0; j < i; j++) {
                if ((nums[i] & nums[j]) == 0) {
                    ans = max(ans, int(words[i].size() * words[j].size()));
                }
            }
        }
        return ans;
    }
};

示例说明

示例一

输入：

["a","ab","abc","d","cd","bcd","abcd"]

输出：

4

解释：

其中一组最长的不同单词为 "ab" 和 "cd"，其长度之和为 4。

示例二

输入：

["a","aa","aaa","aaaa"]

输出：

0

解释：

无法找到两个不同的单词，因此输出 0。