【C++】文字列が指定されたパターンに従っているかどうかを判定するプログラム

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

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

解法のアプローチ

この問題は、パターンと単語列をそれぞれ「初出順の番号列」に変換し、2つの番号列が一致するかを比較することで解けます。手順は次の通りです。

• istringstream を使って str を空白区切りで読み込み、単語を配列 words に格納する
• マップ p2i を用意し、パターン内の各文字に初めて出現した順に 1, 2, 3, … と番号を割り当て、その番号を連結した文字列 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

計算量の目安

時間計算量は O(n)、空間計算量も O(n)（n はパターンの長さおよび単語の総数）です。unordered_map による参照は平均定数時間で行えるため、大きな入力に対しても効率的に動作します。