C++での単語の長さの最大積

wordsという文字列配列があるとします。length（word [i]）* length（word [j]）の最大値を見つけます。ここで、2つの単語は共通の文字を共有しません。各単語には小文字のみが含まれると想定できます。そのような2つの単語が存在しない場合は、0を返します。したがって、入力が[“ abcw”、“ baz”、“ foo”、“ bar”、“ xtfn”、“ abcdef”]の場合、出力は16になります。 2つの単語は「abcw」、「xtfn」の場合があります。

これを解決するには、次の手順に従います-

• getRev（）というメソッドを定義します。これはxを入力として受け取ります

• ret：=0

• 0から25の範囲のiの場合

  • x /（2 ^ i）が偶数の場合、ret：=ret OR 2 ^ i

• retを返す

• メインの方法から、次のようにします-

• 1つのマップを作成しますmn：=単語配列のサイズ

• 0からn–1の範囲のiの場合

  • s：=words [i]、key：=0

  • 0からsのサイズまでの範囲のjの場合

    • key：=key OR 2 ^（s [j] –「a」のASCII）

  • m [i]：=キー

• ret：=0

• 0から単語のサイズまでの範囲のiの場合-1

  • 範囲iのjの場合+1サイズの単語– 1

    • m [i] AND m [j] =0の場合、ret：=単語のサイズの最大値[i]*単語のサイズ[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