Leetcode: Word pattern (0ms)

Difficulty: Easy

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Hash Table

Show Similar Problems

---------------------------------------

---------------------------------------

1. Using two hash table to record the frequency map. Note that we should check every time when updating the frequency map as:

  a   a   b.....

  aa bb aa.....

has the same frequency map but the mapping is wrong!

2. A good way to extract the string from "aa bb aa ....." is to use "istringstream", some notes about how to use it:

//////////////////////////////////////////

       string str = "qq cc ddd";

       istringstream stream(str);

       int a;

       while (stream >> a){

              cout << a << endl;

       }

///////////////////////////

The output will be 

qq

cc

ddd

And then the loop will terminate automatically. 

///////////////////////////////////////////////////////////////

//codes

       class Solution {

       public:

              bool wordPattern(string pattern, string str) {

                     map<char, int> pat;

                     map<string, int> st;

                     istringstream istr(str);

                     string tmp;

                     int i = 0;

                     while (istr >> tmp){

                           //if # of pattern is shorter

                           if (i == pattern.size())return false;

                           //compose the frequency map

                           pat[pattern[i]]++;

                           st[tmp]++;

                           //check frequency for each step

                           if (pat.find(pattern[i])->second != st.find(tmp)->second)return false;

                           i++;

                     }

                     //if # of pattern is longer

                     if (i<pattern.size())return false;

                     return true;

              }

       };