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

問題の概要

ある文字列に対して、各文字をその次の文字へ「シフト」する操作を考えます。たとえば「abc」は「bcd」に変換でき、この操作を繰り返すことで「abc」→「bcd」→ … →「xyz」という一連のシフト系列が形成されます。ここで、小文字の英字のみから構成される空でない文字列のリストが与えられたとき、同じシフト系列に属する文字列どうしをすべてグループにまとめることが求められます。

たとえば、入力が ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"] の場合、出力は [["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"]] となります。「abc」「bcd」「xyz」はいずれも同じシフト系列に属するため、同一のグループに分類されます。

解法のアプローチ

この問題を解くうえでの鍵は、「同じシフト系列に属する文字列は、隣接する文字同士の差分パターンが必ず一致する」という性質です。そこで、各文字列から差分パターンをキーとして生成し、ハッシュマップを用いてグループ化を行います。具体的な手順は以下の通りです。

• マップ m を1つ定義します。
• 結果を格納する2次元配列 ret を定義します。
• i を 0 から文字列リストのサイズ未満まで1ずつ増やしながら、以下を繰り返します。
  • key を空文字列で初期化します。
  • j を 1 から strings[i] のサイズ未満まで1ずつ増やしながら、以下を繰り返します。
    • diff := strings[i][j] − strings[i][j−1](隣接文字の差分)を計算します。
    • diff が負になる場合は diff := diff + 26 として正規化します(末尾の z から先頭の a への折り返しに対応)。
    • key に「#」と diff の文字列表現を連結します。
  • m[key] の末尾に strings[i] を追加します。
• m 内の各要素 it について、その値を ret の末尾に追加します。
• ret を返します。

なぜ差分パターンがキーとして機能するのか

「abc」の差分は [1, 1] であり、「bcd」も同じく [1, 1] です。「xyz」のように z を超えて折り返す場合でも、26 で正規化すれば [1, 1] となります。また「az」は [25]、「ba」も折り返しを考慮すると [25] になり、同じキーに分類されます。このように差分パターンは文字列の絶対的な位置に依存せず、シフト関係のみを表す「指紋」として機能するのです。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#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"}

出力

[[abc, bcd, xyz],[az, ba],[a, z],[acef]]

※ unordered_map を使用しているため、出力されるグループの並び順は実行環境によって異なることがあります。

計算量の評価

文字列の個数を n、最長の文字列長を k とすると、各文字列のキー生成に O(k) かかるため、全体の時間計算量は O(n × k)、必要な空間計算量も O(n × k) となります。すべての文字列ペアを直接比較する素朴な手法(O(n² × k))と比べて、大幅に効率的である点がこのアプローチの大きな魅力です。