C++で解く単語パターン問題：文字列がパターンに従うかを判定する方法

問題概要

パターン pattern と文字列 str が与えられたとき、str がそのパターンに従っているかどうかを判定します。ここで「従う」とは、パターン中の各文字と、文字列中の空でない各単語との間に全単射（一対一対応）が成り立つことを意味します。

たとえば、pattern = "cbbc"、str = "word pattern pattern word" の場合、文字 'c' が単語 "word" に、文字 'b' が単語 "pattern" に対応しているため、結果は True となります。

解き方の考え方

この問題は、パターン側と単語側をそれぞれ「数値の並び」に正規化して比較するのが有効です。具体的な手順は以下の通りです。

• istringstream を使って文字列 str を空白区切りで読み込み、単語を順に配列 words へ格納します。

• マップ p2i を用意し、パターンの各文字を先頭から走査します。初めて現れた文字には新しい通し番号 i を割り当て、その番号を文字列 pat の末尾に連結していきます。これにより、同じ文字は必ず同じ番号に、異なる文字は異なる番号に対応します。

• 同様に、マップ str2i を用意し、単語配列 words の各要素を走査して、番号の並び pat1 を作成します。

• 最後に pat と pat1 が一致すれば true、そうでなければ false を返します。

この手法により、全単射の条件（同じ文字と同じ単語の対応関係が一対一で保たれること）を自然に検証できます。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool wordPattern( string pattern, string str ) {
        istringstream strcin(str);
        string word;
        vector<string> words;
        while (strcin >> word)
            words.push_back(word);
        unordered_map<char, int> p2i;
        int i = 0;
        string pat = "";
        for (auto c : pattern) {
            if (p2i.count(c) == 0) {
                i++;
                p2i[c] = i;
            }
            pat += to_string(p2i[c]);
        }
        unordered_map<string, int> str2i;
        i = 0;
        string pat1 = "";
        for (auto c : words) {
            if (str2i.count(c) == 0) {
                i++;
                str2i[c] = i;
            }
            pat1 += to_string(str2i[c]);
        }
        return pat1 == pat;
    }
};
main(){
    Solution ob;
    cout << (ob.wordPattern("cbbc", "word pattern pattern word"));
}

入力

"cbbc", "word pattern pattern word"

出力

1

まとめ

本記事では、パターンと文字列が全単射の関係にあるかを判定する「単語パターン」問題を取り上げました。ハッシュマップ（unordered_map）を使って文字・単語をそれぞれ番号列へ変換し、あとは文字列の一致比較だけで答えを求められるのがポイントです。各文字・各単語を一度ずつ処理するだけで済むため、全体の計算量はほぼ O(n) と非常に効率的です。文字列処理とマップ操作の組み合わせを学ぶのに最適な演習問題といえるでしょう。