C++에서 이동된 문자열 그룹화

문자열이 있다고 가정하고 각 문자를 연속 문자로 "이동"할 수 있으므로 "abc"를 "bcd"로 변경할 수 있습니다. "abc" -> "bcd" -> ... -> "xyz" 시퀀스를 형성하는 이 작업을 계속 수행할 수 있습니다. 소문자 알파벳만 포함하는 비어 있지 않은 문자열 목록이 있는 경우 동일한 이동 시퀀스에 속하는 모든 문자열을 그룹화해야 합니다.

따라서 입력이 ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]와 같으면 출력은 [ ["abc ","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 맵 정의

• 하나의 2D 배열 ret 정의

• initialize i :=0의 경우, i <문자열의 크기일 때 업데이트(i를 1만큼 증가), 수행 -

  • 키 :=빈 문자열

  • j 초기화의 경우:=1, j <문자열의 크기[i]일 때 업데이트(j를 1만큼 증가), 수행 -

    • diff :=문자열[i, j] - 문자열[i, j - 1]

    • diff <0이면 -

      • 차이 :=차이 + 26

    • key :=key concatenate "#" diff를 문자열로 연결

  • m[key]

    끝에 문자열[i] 삽입

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