ผลิตภัณฑ์สูงสุดของความยาวคำใน C++

สมมติว่าเรามีอาร์เรย์สตริงที่เรียกว่าคำ ให้หาค่าสูงสุดของ length(word[i]) * length(word[j]) โดยที่ทั้งสองคำจะไม่ใช้ตัวอักษรร่วมกัน เราสามารถสรุปได้ว่าแต่ละคำจะมีเฉพาะตัวพิมพ์เล็กเท่านั้น หากไม่มีสองคำดังกล่าว ให้คืนค่า 0 ดังนั้นหากอินพุตเป็น ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] ผลลัพธ์จะเป็น 16 เนื่องจากคำสองคำสามารถเป็น “abcw”, “xtfn” ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า getRev() ซึ่งจะใช้ x เป็นอินพุต

• ยกเลิก :=0

• สำหรับผมอยู่ในช่วง 0 ถึง 25

  • ถ้า x / (2^i) เป็นคู่ ดังนั้น ret :=ret OR 2^i

• รีเทิร์น

• จากวิธีหลัก ให้ทำดังนี้ −

• สร้างหนึ่งแผนที่ m n :=ขนาดของอาร์เรย์คำ

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • s :=คำ[i], คีย์ :=0

  • สำหรับ j ในช่วง 0 ถึงขนาดของ s

    • คีย์ :=คีย์ OR 2^(s[j] – ASCII ของ 'a')

  • m[i] :=คีย์

• ยกเลิก :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของคำ - 1

  • สำหรับ j ในช่วง i + 1 ขนาดคำ – 1

    • ถ้า m[i] AND m[j] =0 แล้ว ret :=สูงสุดของขนาดของ word[i] * ขนาดของ word[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