C++で解く単語パターンII：バックトラッキングによる全単射マッチングの実装

問題概要

パターン文字列と、もうひとつの文字列 str が与えられます。str がこのパターンに従っているかどうかを判定してください。ここで「パターンに従う」とは完全一致を意味し、パターン中の各文字と str 中の空でない部分文字列との間に、全単射（一対一対応）が成立していなければなりません。

たとえば、パターンが "abaa"、str が "orangegreenorangeorange" の場合を見てみましょう。a → "orange"、b → "green" という対応が成り立ち、"abaa" が "orangegreenorangeorange" と完全に一致するため、出力は true になります。

解法のアプローチ：バックトラッキング

この問題は、バックトラッキング（試行の巻き戻し）を用いた再帰的な探索によって解くことができます。再帰関数 solve() を定義し、以下の手順で処理を進めます。

1. 関数 solve() を定義します。引数としてインデックス i、j、パターン ptr、文字列 s、文字と部分文字列の対応を保持するマップ m、使用済みの部分文字列を記録するセット used を受け取ります。
2. i が s のサイズ以上かつ j が ptr のサイズ以上の場合、true を返します（文字列とパターンの両方を消費し切った＝マッチ成功）。
3. i が s のサイズ以上、または j が ptr のサイズ以上の場合、false を返します（どちらか一方だけが余ってしまった＝失敗）。
4. ptr[j] がすでにマップ m に登録されている場合：
   • req := m[ptr[j]] とし、len := req の長さとします。
   • len が s の残りの長さより大きければ、false を返します。
   • s のインデックス i から始まる長さ len の部分文字列が req と一致し、かつ solve(i + len, j + 1, ptr, s, m, used) が true を返せば、true を返します。
   • それ以外は false を返します。
5. ptr[j] がまだマップに存在しない場合：
   • x := ptr[j] とします。
   • k を i から s のサイズ未満まで 1 ずつ増やしながらループします。
     • temp := s のインデックス i から長さ (k − i + 1) の部分文字列とします。
     • temp がすでに used に含まれている場合は、以降の処理をスキップして次の反復へ進みます（全単射を保つため、同じ部分文字列の再利用は禁止です）。
     • m[x] := temp としてマップに登録し、used に temp を挿入します。
     • solve(k + 1, j + 1, ptr, s, m, used) が true を返せば、true を返します。
     • そうでなければ、m から x を削除し、used から temp を削除して状態を元に戻します（バックトラック）。
6. すべての候補が失敗した場合は false を返します。

メイン側では、空のマップ m と空のセット used を用意し、solve(0, 0, ptr, s, m, used) の結果を返すだけで完了です。

なお、この手法の最悪計算量は O(n^m)（n は文字列の長さ、m はパターンの長さ）と指数オーダーになりますが、used セットによる枝刈り（同一部分文字列の再利用防止）が探索空間を大きく削減し、実用上は高速に動作します。

C++ 実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool solve(int i, int j, string ptr, string s, map <char, string>& m, set<string>& used){
        if (i >= s.size() && j >= ptr.size()) {
            return true;
        }
        if (i >= s.size() || j >= ptr.size())
            return false;
        if (m.count(ptr[j])) {
            string req = m[ptr[j]];
            int len = req.size();
            if (len > s.size() - i)
                return false;
            if ((s.substr(i, len) == req) && solve(i + len, j + 1, ptr, s, m, used))
                return true;
            return false;
        }
        else {
            char x = ptr[j];
            for (int k = i; k < s.size(); k++) {
                string temp = s.substr(i, k - i + 1);
                if (used.count(temp))
                    continue;
                m[x] = temp;
                used.insert(temp);
                if (solve(k + 1, j + 1, ptr, s, m, used))
                    return true;
                m.erase(x);
                used.erase(temp);
            }
        }
        return false;
    }
    bool wordPatternMatch(string ptr, string s) {
        map<char, string> m;
        set<string> used;
        return solve(0, 0, ptr, s, m, used);
    }
};
main(){
    Solution ob;
    cout << (ob.wordPatternMatch("abaa", "orangegreenorangeorange"));
}

入力例

"abaa" "orangegreenorangeorange"

出力例

1