Word Pattern | Leetcode Top Interview 150

Here we will discuss the most important data structures and algorithms questions which are usually asked in the top rated product based companies.
About me - My name is Anurag Gupta. I have done my B.Tech. from IIT Roorkee. I have done software engineer internship at Amazon and I have 3 years of work experience as a Senior Software Engineer.

Problem description - 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. Specifically:

Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.

#coding #india #indian #code #learning #leetcode #youtube #instagram #software #job #engineering #engineer #algorithm #datastructures #data

[CodingWithAnurag-]

Solution code -
class Solution {
public:
bool wordPattern(string pattern, string s) {
map<char, string> m;
map<string, char> revm;
int np = pattern.length(), ns = s.length();
string temp = "";
int j= 0; // j represents the index of the string pattern.
for (int i=0;i<ns;i++) {
if (s[i] == ' ') {
if(m.find(pattern[j]) != m.end()) {
if (m[pattern[j]] != temp) {
return false;
}
if (revm[temp] != pattern[j]) {
return false;
}
} else if (revm.find(temp) != revm.end()) {
if (revm[temp] != pattern[j]) {
return false;
}
if (m[pattern[j]] != temp) {
return false;
}
} else {
m[pattern[j]] = temp;
revm[temp] = pattern[j];
}
j++;
if (j==np) {
return false;
}
temp = "";
} else {
temp += s[i];
}
}
if(m.find(pattern[j]) != m.end()) {
if (m[pattern[j]] != temp) {
return false;
}
if (revm[temp] != pattern[j]) {
return false;
}
} else if (revm.find(temp) != revm.end()) {
if (revm[temp] != pattern[j]) {
return false;
}
if (m[pattern[j]] != temp) {
return false;
}
} else {
m[pattern[j]] = temp;
revm[temp] = pattern[j];
}
j++;
if (j != np) {
return false;
}
return true;
}
};