Word Pattern challenge in LeetCode

I solved this problem from LeetCode:


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:


pattern = "abba", str = "dog cat cat dog" should return true.


pattern = "abba", str = "dog cat cat fish" should return false.


pattern = "aaaa", str = "dog cat cat dog" should return false.


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.

I was able to solve this problem by using a Dictionary to keep track of the relation between the pattern and the str:

public class Solution {
public bool WordPattern(string pattern, string str)
    {
        var result = str.Split(' ').ToList();
        var mapPattern = new Dictionary();
        if (result.Count != pattern.Count())
        {
            return false;
        }
        string matchstr;
        int index = 0;
        foreach (var c in pattern)
        {
            if (mapPattern.TryGetValue(pattern[index], out matchstr))
            {
                if (matchstr != result[index])
                {
                    return false;
                }
            }
            else 
            {
                if(mapPattern.ContainsValue(result[index]))
                {
                    return false;
                }
                mapPattern.Add(c, result[index]);
            }
            ++index;
        }
        return true;
    }
}

The approach I have currently looks up the Dictionary twice to see if it already exists as a key or as a value in the Dictionary, which I believe would be the reason for slowing this by a significant amount.

Can you determine if I can do away with looking up twice? This solution only runs better than around 36% of the othe

Overall, this is a nice, clean solution, congratulations!

Performance


Can you suggest If I can do away with looking up twice. Currently this solution only runs better that around 36% of the other submissions for this current problem. So, I believe there must be a better and faster way.

"Looking up twice" is not the appropriate term. You do one lookup by key, and another lookup by value. These are very different operations, and lumping them together as "two lookups" hides important details. Imagine a program that does one lookup in an array and one lookup with a Google search on the internet, and the author would wonder if slowness might be caused by doing "two lookups". It would hide a crucial detail that one of the "lookups" is clearly much slower than the other.

The lookup in the dictionary by key is very fast, an \$O(1)\$ operation.

The lookup by value in a typical dictionary (or hash map) implementation is much slower, \$O(n)\$, because dictionaries are indexed by key, not by value. They are designed for fast lookups by key, not by value.

To make the lookup by value faster, you can add a set for values.

Scope

It's good to limit the scope of variables to the minimum needed.

• matchstr should be declared inside the loop, as it is not needed outside

• mapPattern should be initialized after the early return, as it might not be needed

StackExchange Code Review Q#148053, answer score: 3