C++での単語パターン

パターンと文字列strがあるとし、strが同じパターンに従うかどうかを調べます。ここで続くとは、パターン内の文字とstr内の空でない単語の間に全単射があることを意味します。

したがって、入力がpattern ="cbbc"、str ="word pattern pattern word"のような場合、出力はTrueになります。

これを解決するには、次の手順に従います-

• strcin：=str

• 単語の配列を定義する

• strcinの単語ごとに

  • 単語の最後に単語を挿入

• 1つのマップp2iを定義する

• i：=0

• pat：=空の文字列

• パターン内のcの場合-

  • cがp2iのメンバーでない場合、-

    • （iを1増やします）

    • p2i [c]：=i

  • pat：=pat concatenate p2i [c]

• 1つのマップstr2iを定義する

• i：=0

• pat1：=空白の文字列

• 言葉でcの場合-

  • cがstr2iのメンバーでない場合、-

    • （iを1増やします）

    • str2i [c]：=i

  • pat1：=pat1連結str2i[c]

• pat1がpatと同じ場合はtrueを返します

例

理解を深めるために、次の実装を見てみましょう-

#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