C++에서 단어 길이의 최대 곱

<시간/>

단어라는 문자열 배열이 있다고 가정하고 두 단어가 공통 문자를 공유하지 않는 length(word[i]) * length(word[j]) 의 최대값을 찾습니다. 각 단어에는 소문자만 포함된다고 가정할 수 있습니다. 그런 두 단어가 없으면 0을 반환합니다. 따라서 입력이 ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]와 같으면 출력은 16이 됩니다. 두 단어로 "abcw", "xtfn"이 될 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

getRev()라는 메서드를 정의하면 x가 입력으로 사용됩니다.
ret :=0
0에서 25 사이의 i에 대해
- x / (2^i)가 짝수이면 ret :=ret OR 2^i
리턴 렛
기본 방법에서 다음을 수행하십시오 -
하나의 맵 생성 m n :=단어 배열의 크기
0 ~ n – 1 범위의 i에 대해
- s :=단어[i], 키 :=0
- 범위 0에서 s 크기까지의 j에 대해
  - key :=key OR 2^(s[j] – 'a'의 ASCII)
- m[i] :=키
ret :=0
범위 0에서 단어 크기 - 1에 있는 i의 경우
- 범위 i + 1 단어 크기 – 1의 j
  - m[i] AND m[j] =0이면 ret :=단어[i]의 최대 크기 * 단어[j]의 크기
리턴 렛

예시(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"]