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[] words = s.Split(' ');
if (pattern.Length != words.Length)
{
return false;
}
Dictionary<char, string> charToWordMap = new Dictionary<char, string>();
HashSet<string> appearedWordsSet = new HashSet<string>();
for (int i = 0; i < pattern.Length; ++i)
{
if (charToWordMap.ContainsKey(pattern[i]))
{
if (charToWordMap[pattern[i]] != words[i])
{
return false;
}
}
else
{
if (appearedWordsSet.Contains(words[i]))
{
return false;
}
charToWordMap.Add(pattern[i], words[i]);
appearedWordsSet.Add(words[i]);
}
}
return true;
}
Complexity: O(n)
No comments:
Post a Comment