Pankaj Tanwar
Published on

Word Pattern.

––– views

Problem of the day - Word Pattern

Tag - Easy

Given a pattern and a string s, find if s 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 s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog" Output: true

I am not gonna lie, at first glance the problem seemed very tricky. But when I looked at the related tag hash table, It was the light bulb moment for me.

But, there is some catch.

  1. I need to track, for each text in the pattern, respective word in string s, must always be the same.
  2. And, vice versa too. For each respective word, it must follow the same pattern. (eg - ab - dog cat )
  3. Length of pattern must be same to number of words in string s

After considering all the edge cases, I was able to submit it with 0ms run time, passing 100% C++ submissions.

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        int patt_ind = 0;
        int total_words = 0;
        string word = "";
        map<char, string> list;
        map<string, char> rev_list;
        char element;


        for(char c: s) {
            if(c == ' ') {
                element = pattern[patt_ind];
                if(list[element] != "" && list[element] != word) return false;
                if(rev_list[word] && rev_list[word] != element) return false;
                list[element] = word;
                rev_list[word] = element;
                word = "";
                patt_ind++;
                total_words++;
            } else {
                word += c;
            }
        }
        element = pattern[patt_ind];
        if(list[element] != "" && list[element] != word) return false;
        if(rev_list[word] && rev_list[word] != element) return false;
        if(total_words + 1 != pattern.length()) return false;
        return true;
    }
};

That was a pretty good problem. See you guys tomorrow!

If you feel, I am missing on something, feel free to reach out to me

I welcome your suggestions to improve it further!

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary

Tweet this article