hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

290. Word Pattern


  • Approach:

    1. Declared two unordered_map (HashMap). One for mapping each word to a single character and the other for each character to every single word.

    2. Return false if the total number of words in s is not equal to the total number of characters in the pattern.

    3. Now, while traversing through each word of s and each character from pattern, do the following things -

      • Firstly, check if both ith character of pattern and word of s has been already assigned with something.

      • If they are not assigned, then map them bidirectionally (that is word[i] => pattern[i] in a map and pattern[i] => word[i] in another map)

      • If they are already assigned, then check if word[i] is assigned to pattern[i] and pattern[i] is assigned to word[i].

      • If not then return false. Otherwise, keep checking for the rest of the words and patterns.

    4. Return true at the end as all of the false cases are covered.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N), N = Length of pattern


Code [C++]

class Solution {

public:

bool wordPattern(string pattern, string s) {

vector<string>words;

stringstream ss(s);

while(ss >> s){

words.push_back(s);

}

int n = pattern.size();

if(n != words.size()) return false;


unordered_map<char, string>mymap;

unordered_map<string, char>checkMap;

for(int i=0; i<n; i++){

if(mymap.find(pattern[i]) == mymap.end() && checkMap.find(words[i]) == checkMap.end()){

mymap[pattern[i]] = words[i];

checkMap[words[i]] = pattern[i];

}

else{

if((mymap[pattern[i]] != words[i]) || checkMap[words[i]] != pattern[i]) return false;

}

}

return true;

}

};