Word Pattern

Problem: Following the pattern means a full match, such that there is a bijection between a letter in pattern and a non-empty word in the input string.

Example:

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

Approach: We can use hashing here. We can maintain a hash where key is the character is pattern and value is word in s. Whenever a we encounter a new character, we can add it in to the hash as key and corresponding word as value. if we get a character which is already in hash then we can check if the corresponding value in the hash and the current word are same or not, if they are not same then we will return false immediately.

The approach looks good and also works on examples like given in the problem description but It won't work on inputs like [pattern = "abba", s = "cat cat cat cat"].  Here if you see by going with above approach we will return true and the actual answer is false.

What we can do in such cases? We can maintain a reverse hash with key as word and value as character to just reverify if the current word is already a value for a different character in the pattern.  

This will solve our whole problem.

Implementation in C#:

    public bool WordPattern(string pattern, string s)

    {

        string[] sArr = s.Split(' ');

        int length = pattern?.Length ?? 0;

        if (length != sArr.Length)

        {

            return false;

        }

        var map = new Dictionary<char, string>();

        var usedWords = new HashSet<string>();

        for (int i = 0; i < length; ++i)

        {

            if (map.ContainsKey(pattern[i]))

            {

                if (map[pattern[i]] != sArr[i])

                {

                    return false;

                }

            }

            else

            {

                if (usedWords.Contains(sArr[i]))

                {

                    return false;

                }

                map[pattern[i]] = sArr[i];

                usedWords.Add(sArr[i]);

            }

        }

        return true;

    }

Complexity: O(n)