मान लीजिए हमारे पास words नामक एक स्ट्रिंग सरणी है, length(word[i]) * length(word[j]) का अधिकतम मान ढूंढें जहां दो शब्द सामान्य अक्षर साझा नहीं करेंगे। हम मान सकते हैं कि प्रत्येक शब्द में केवल लोअरकेस अक्षर होंगे। यदि ऐसी कोई दो शब्द मौजूद नहीं हैं, तो 0 लौटाएं।
उदाहरण के लिए, यदि इनपुट ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] जैसा है, तो आउटपुट 16 होगा, क्योंकि दो शब्द "abcw", "xtfn" हो सकते हैं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
getRev()नामक एक विधि परिभाषित करें, यहxइनपुट के रूप में लेगाret := 0iको 0 से 25 तक लूप करें- यदि
x / (2^i)सम है, तोret := ret OR 2^i
- यदि
retलौटाएं- मुख्य विधि से, निम्नलिखित करें:
mनामक एक मैप बनाएंn := words सरणी का आकारiको 0 सेn - 1तक लूप करेंs := words[i],key := 0jको 0 सेs के आकारतक लूप करेंkey := key OR 2^(s[j] - 'a' का ASCII)
m[i] := key
ret := 0iको 0 सेwords के आकार - 1तक लूप करेंjकोi + 1सेwords के आकार - 1तक लूप करें- यदि
m[i] AND m[j] = 0, तोret := word[i] का आकार * word[j] का आकार का अधिकतम
- यदि
retलौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> 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