กลุ่ม Shifted Strings ใน C ++

สมมติว่าเรามีสตริง เราสามารถ "เปลี่ยน" ตัวอักษรแต่ละตัวเป็นตัวอักษรต่อเนื่องกันได้ ดังนั้น:"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 <ขนาดของสตริง, อัปเดต (เพิ่ม i ขึ้น 1), ทำ -

  • คีย์ :=สตริงว่าง

  • สำหรับการเริ่มต้น j :=1 เมื่อ j

    • diff :=strings[i, j] - strings[i, j - 1]

    • ถ้าต่าง <0 แล้ว −

      • ต่าง :=ต่าง + 26

    • key :=key concatenate "#" concatenate diff เป็นสตริง

  • ใส่ strings[i] ต่อท้าย m[key]

• สำหรับแต่ละองค์ประกอบในหน่วย m ให้ทำ -

  • แทรกค่าของมันที่ส่วนท้ายของ ret

  • (เพิ่มขึ้นอีก 1)

• รีเทิร์น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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, ],]