C ++中字长的最大乘积

假设我们有一个称为单词的字符串数组,找到length(word [i])* length(word [j])的最大值,其中两个单词将不共享公共字母。我们可以假设每个单词仅包含小写字母。如果不存在这两个词,则返回0。因此,如果输入类似于[“ abcw”,“ baz”,“ foo”,“ bar”,“ xtfn”,“ abcdef”],则输出将为16因为两个词可以是“ abcw”,“ xtfn”。

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个名为的方法getRev(),它将x作为输入

  • ret:= 0

  • 当我在0到25的范围内

    • 如果x /(2 ^ i)是偶数,则ret:= ret OR 2 ^ i

  • 返回ret

  • 从主要方法中,执行以下操作-

  • 创建一个映射mn:=单词数组的大小

  • 对于i,范围为0至n – 1

    • 键:=键或2 ^(s [j] –'a'的ASCII)

    • s:= words [i],key:= 0

    • 对于范围在0到s大小之间的j

    • m [i]:=键

  • ret:= 0

  • 对于我来说,范围是0到字数-1

    • 如果m [i]和m [j] = 0,则ret:=单词[i]的最大大小*单词[j]的大小

    • 对于范围i + 1的单词大小– 1

  • 返回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

以上是 C ++中字长的最大乘积 的全部内容, 来源链接: utcz.com/z/338465.html

回到顶部