मान लीजिए हमारे पास एक स्ट्रिंग है, हम इसके प्रत्येक अक्षर को उसके अगले अक्षर में "शिफ्ट" कर सकते हैं, जैसे: "abc" को "bcd" में बदला जा सकता है। हम इस ऑपरेशन को बार-बार कर सकते हैं जिससे अनुक्रम बनता है: "abc" → "bcd" → ... → "xyz"। यदि हमारे पास लोअरकेस अल्फाबेट वाली नॉन-खाली स्ट्रिंग्स की सूची है, तो हमें उन सभी स्ट्रिंग्स को ग्रुप करना है जो एक ही शिफ्टिंग अनुक्रम से संबंधित हैं।
इसलिए, यदि इनपुट है ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], तो आउटपुट होगा [ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक मैप m परिभाषित करें
एक 2D ऐरे ret परिभाषित करें
i := 0 से शुरू करें, जब i < strings का आकार, i बढ़ाते हुए, करें -
key := खाली स्ट्रिंग
j := 1 से शुरू करें, जब j < strings[i] का आकार, j बढ़ाते हुए, करें -
diff := strings[i, j] - strings[i, j - 1]
यदि diff < 0, तो -
diff := diff + 26
key := key + "#" + diff को स्ट्रिंग के रूप में
strings[i] को m[key] के अंत में डालें
m के प्रत्येक एलिमेंट it के लिए, करें -
it के मान को ret के अंत में डालें
(it को बढ़ाएं)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: vector<vector<string>> groupStrings(vector<string>& strings) { unordered_map<string, vector<string> > m; vector<vector<string>> ret; for (int i = 0; i < strings.size(); i++) { string key = ""; for (int j = 1; j < strings[i].size(); j++) { int diff = strings[i][j] - strings[i][j - 1]; if (diff < 0) diff += 26; key += "#" + to_string(diff); } m[key].push_back(strings[i]); } unordered_map<string, vector<string>>::iterator it = m.begin(); while (it != m.end()) { ret.push_back(it->second); it++; } return ret; } }; main(){ Solution ob; vector<string> v = {"abc","bcd","acef","xyz","az","ba","a","z"}; print_vector(ob.groupStrings(v)); }इनपुट
{"abc","bcd","acef","xyz","az","ba","a","z"}आउटपुट
[[az, ba, ],[a, z, ],[abc, bcd, xyz, ],[acef, ],]
