C++でシフトされた文字列をグループ化する

文字列があるとすると、各文字を連続する文字に「シフト」できるため、「abc」を「bcd」に変更できます。 「abc」->「bcd」->...->「xyz」のシーケンスを形成するこの操作を続行できます。小文字のアルファベットのみを含む空でない文字列のリストがある場合は、同じシフトシーケンスに属するすべての文字列をグループ化する必要があります。

したがって、入力が["abc"、 "bcd"、 "acef"、 "xyz"、 "az"、 "ba"、 "a"、 "z"]の場合、出力は[["abc "、" bcd "、" xyz "]、[" az "、" ba "]、[" acef "]、[" a "、" z "]]

これを解決するには、次の手順に従います-

• 1つのマップを定義するm

• 1つの2D配列retを定義する

• 初期化i：=0の場合、i <文字列のサイズの場合、更新（iを1増やします）、実行-

  • キー：=空白の文字列

  • 初期化j：=1の場合、j <文字列のサイズ[i]の場合、更新（jを1増やします）、実行-

    • diff：=文字列[i、j]-文字列[i、j-1]

    • diff <0の場合、-

      • diff：=diff + 26

    • key：=key concatenate "＃" concatenate diff as string

  • m [key]

    の最後にstrings[i]を挿入します

• mの要素ごとに、次のようにします-

  • retの最後にその値を挿入します

  • （1つ増やします）

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