Program to check whether given words are maintaining given pattern or not in C++

Suppose we have a pattern p and a string str, we have to check whether str follows the same pattern or not. Here follow means there is a bijection between a letter in pattern and a non-empty word in str.

So, if the input is like pattern = "cbbc", str = "word pattern pattern word", then the output will be True.

To solve this, we will follow these steps −

• strcin := str

• Define an array words

• for each word in strcin

  • insert word at the end of words

• Define one map p2i

• i := 0

• pat := empty string

• for c in pattern −

  • if c is not member of p2i, then −

    • (increase i by 1)

    • p2i[c] := i

  • pat := pat concatenate p2i[c]

• Define one map str2i

• i := 0

• pat1 := blank string

• for c in words −

  • if c is not member of str2i, then −

    • (increase i by 1)

    • str2i[c] := i

  • pat1 := pat1 concatenate str2i[c]

• return true when pat1 is same as pat

Example  

Let us see the following implementation to get a better understanding −

 Live Demo

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

Input

"cbbc", "word pattern pattern word"

Output

1