返回

[Leetcode]318. Maximum Product of Word Lengths(C++)

题目描述

题目链接:318. Maximum Product of Word Lengths

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

例子

例子 1

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".

例子 2

Input: words = ["a","ab","abc","d","cd","bcd","abcd"] Output: 4 Explanation: The two words can be "ab", "cd".

例子 3

Input: words = ["a","aa","aaa","aaaa"] Output: 0 Explanation: No such pair of words.

Constraints

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i] consists only of lowercase English letters.

解题思路

这道题思路比较直观,对于每一个单词首先用一个哈希表来存储出现过的字母。然后进行二层遍历,比较所有可能的单词对,对每一对单词依次查看每个字母是否在两个单词出现过,如果没有的话则将其长度乘积与当前结果取最大值。最后返回结果即可,代码如下:

#include <string>
#include <vector>

class Solution {
public:
    int maxProduct(std::vector<std::string>& words) {
        int n = words.size();
        bool letters[n][26];
        for (int i = 0; i < n; ++i) {
            memset(letters[i], 0, 26);
            std::string word = words[i];
            for (char l : word) {
                letters[i][l - 'a'] = true;
            }
        }

        int max_len = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                bool shared = false;
                for (int k = 0; k < 26; ++k) {
                    if (letters[i][k] && letters[j][k]) {
                        shared = true;
                        break;
                    }
                }

                if (!shared) {
                    max_len = std::max(
                        static_cast<int>(words[i].length() * words[j].length()),
                        max_len);
                }
            }
        }
        return max_len;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 318.MaximumProductOfWordLengths.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy