Blogs Hub

Word Pattern - Hash Table - Easy - LeetCode - MiniTV

Word Pattern - Hash Table - Easy - LeetCode - मिनी टीवी

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
Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Example 4:

Input: pattern = "abba", s = "dog dog dog dog"
Output: false
 

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lower-case English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

public class Solution {
    public bool WordPattern(string pattern, string s) {
        var words = s.Split(' ');
        if(pattern.Length!=words.Length){
            return false;
        }
        var map = new Dictionary<char,string>();
        var map2 = new Dictionary<string,char>();
        for(int i=0;i<words.Length;i++){
            if(!map.ContainsKey(pattern[i])){
                map.Add(pattern[i],words[i]);
            }
            if(!map2.ContainsKey(words[i])){
                map2.Add(words[i],pattern[i]);
            }
        }
        
        for(int i=0;i<words.Length;i++){
            if(map[pattern[i]]!=words[i]){
                return false;
            }
            
            if(map2[words[i]]!=pattern[i]){
                return false;
            }
        }
        
        return true;
    }
}

 


Time Complexity: O(n)

Space Complexity: O(n)