C++ এ শব্দের দৈর্ঘ্যের সর্বোচ্চ পণ্য

ধরুন আমাদের কাছে শব্দ নামে একটি স্ট্রিং অ্যারে আছে, দৈর্ঘ্য(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 বা 2^i

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• একটি মানচিত্র তৈরি করুন m n :=শব্দ বিন্যাসের আকার

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • s :=শব্দ[i], কী :=0

  • j এর জন্য রেঞ্জ 0 থেকে s এর মাপ

    • কী :=কী বা 2^(s[j] – 'a'-এর ASCII)

  • m[i] :=কী

• ret :=0

• i এর জন্য 0 থেকে শব্দের আকার - 1

  • j-এর জন্য পরিসীমা i + 1 শব্দের আকার – 1

    • যদি 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"]

আউটপুট

16