LC318.最大单词长度乘积

原题链接

思路：位运算

• 位运算：实现O(1)时间判断两个字符串是否有公共字母

• 将每个字母转化成对应的数字，对应位置标记为1，逐个左移即可。

  // 两个字符串是否包含公共字母，操作复杂度可以降到O(1)
  vector<int> nums;
  for (int i = 0, n = words.size(); i < n; ++i) {
    int cur_num = 0;
    for (int j = 0, len = words[i].size(); j < len; ++j) {
        cur_num |= (1<< (words[i][j] - 'a'));
    }
    nums.push_back(cur_num);
  }

• 判断两个字符串是不是有公共字母，只需要进行与运算即可。

  代码

class Solution {
    public:
    int maxProduct(vector<string>& words) {
        // 两个字符串是否包含公共字母，操作复杂度可以降到O(1)
        vector<int> nums;
        for (int i = 0, n = words.size(); i < n; ++i) {
            int cur_num = 0;
            for (int j = 0, len = words[i].size(); j < len; ++j) {
                cur_num |= (1<< (words[i][j] - 'a'));
            }
            nums.push_back(cur_num);
        }
        int max_len = 0;
        for (int i = 0, n = words.size(); i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((nums[i] & nums[j]) == 0) {
                    max_len = max(max_len, int(words[i].size() * words[j].size())) ;
                }
            }
        }
        return max_len;
    }
};