C++ 中单词长度的最大乘积
c++server side programmingprogramming
假设我们有一个名为 words 的字符串数组，求 length(word[i]) * length(word[j]) 的最大值，使得两个单词不包含相同的字母。我们可以假设每个单词只包含小写字母。如果不存在这样的两个单词，则返回 0。因此，如果输入为 [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”]，则输出将为 16，因为两个单词可以是 “abcw” 和 “xtfn”。
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 getRev() 的方法，它将以 x 作为输入
ret := 0
对于 i，范围为 0 到 25
如果 x / (2^i) 为偶数，则ret := ret 或 2^i
return ret
在 main 方法中，执行以下操作 −
创建一个 map m n := 单词数组的大小
for i in range 0 to n – 1
s := words[i], key := 0
for j in range 0 to the size of s
- key := key OR 2^(s[j] – a 的 ASCII 码)
m[i] := key
ret := 0
for i in range 0 to the size of words - 1
for j in range i + 1 of words size – 1
如果 m[i] 且 m[j] = 0，则 ret := word[i] 的大小 * word[j] 的大小之和
返回 ret
示例(C++)
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h&g;
using namespace std;
class Solution {
public:
int getRev(int x){
int ret = 0;
for(int i = 0; i <= 25 ; i++){
if(!((x >> i) & 1)){
ret |= (1 << i);
}
}
return ret;
}
int maxProduct(vector<string>& words) {
unordered_map <int, int> m;
int n = words.size();
for(int i = 0; i < n; i++){
string s = words[i];
int key = 0;
for(int j = 0; j < s.size(); j++){
key |= 1 << (s[j] - 'a');
}
m[i] = key;
}
int ret = 0;
for(int i = 0; i < words.size(); i++){
for(int j = i + 1; j < words.size(); j++){
if((m[i] & m[j]) == 0){
//cout << i << " " << j << endl;
ret = max(ret, (int)words[i].size() * (int)words[j].size());
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};
cout << (ob.maxProduct(v));
}
输入
["abcw","baz","foo","bar","xtfn","abcdef"]
输出
16
