Sản phẩm tối đa của độ dài từ trong C ++

Giả sử chúng ta có một mảng chuỗi được gọi là các từ, hãy tìm giá trị lớn nhất của độ dài (từ [i]) * độ dài (từ [j]) trong đó hai từ sẽ không chia sẻ các chữ cái chung. Chúng ta có thể giả định rằng mỗi từ sẽ chỉ chứa các chữ cái thường. Nếu không có hai từ như vậy tồn tại, thì trả về 0. Vì vậy, nếu đầu vào là [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”], thì đầu ra sẽ là 16, như hai từ có thể là “abcw”, “xtfn”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức có tên getRev (), phương thức này sẽ lấy x làm đầu vào

• ret:=0

• cho tôi trong phạm vi từ 0 đến 25

  • nếu x / (2 ^ i) chẵn thì ret:=ret OR 2 ^ i

• trả lại ret

• Từ phương thức chính, thực hiện như sau -

• Tạo một bản đồ m n:=kích thước mảng từ

• cho tôi trong phạm vi từ 0 đến n - 1

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

  • cho j trong phạm vi 0 đến kích thước của s

    • key:=key OR 2 ^ (s [j] - ASCII của ‘a’)

  • m [i]:=key

• ret:=0

• cho tôi trong phạm vi từ 0 đến kích thước của từ - 1

  • cho j trong phạm vi i + 1 cỡ từ - 1

    • nếu m [i] VÀ m [j] =0, thì ret:=kích thước tối đa của từ [i] * kích thước của từ [j]

• trả lại ret

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

["abcw","baz","foo","bar","xtfn","abcdef"]

Đầu ra

16