LeetCode-318. Maximum Product of Word Lengths

落寞瓜子壳 lv.3

发布时间：2023-12-13 20:54:51 221

相关标签：

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Input:

["abcw","baz","foo","bar","xtfn","abcdef"]

Output:

16 
Explanation:

The two words can be

"abcw", "xtfn"

Example 2:

Input:

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

Output:

4 
Explanation:

The two words can be

"ab", "cd"

Example 3:

Input:

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

Output:

0 
Explanation:

No such pair of words.

题解：

给位运算跪一下好吧orz

class Solution {
public:
  int maxProduct(vector<string>& words) {
    int ans = 0;
    int n = words.size();
    for (int i = 0; i < n; i++) {
      vector<bool> visit(26, 0);
      int li = words[i].size();
      bool dup = false;
      int maxi = 0;
      for (int j = 0; j < li; j++) {
        visit[words[i][j] - 97] = true;
      }
      for (int j = i + 1; j < n; j++) {
        int lj = words[j].size();
        for (int k = 0; k < lj; k++) {
          if (visit[words[j][k] - 97] == true) {
            dup = true;
            break;
          }
        }
        if (dup == false && lj > maxi) {
          ans = max(ans, lj * li);
          maxi = lj;
        }
        dup = false;
      }
    }
    return ans;
  }
};

文章来源： https://blog.51cto.com/u_14150327/5564420

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。