🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires determining if a string s
follows the same pattern as given by pattern
. This means there should be a one-to-one correspondence (bijection) between each character in pattern
and a non-empty word in s
.
Approach
- Split
s
into Words: First, split the strings
into individual words. - Length Check: Check if the number of words matches the length of
pattern
. If they do not match, returnfalse
as it's not possible to have a bijection. - Mapping Creation: Use two dictionaries to create mappings:
- One dictionary to map characters from
pattern
to words froms
. - Another dictionary to map words froms
to characters frompattern
. - Iterate and Map: Iterate through each character in
pattern
and the corresponding word ins
: - Check if the current character inpattern
is already mapped to a different word. - Check if the current word ins
is already mapped to a different character. - If there are any conflicts in the mappings, returnfalse
. - If there are no conflicts, create the mappings in both dictionaries. - Return True:
If all character-word pairs are processed without conflicts, return
true
.
This approach ensures that there is a one-to-one correspondence between each character in pattern
and each word in s
, thereby determining if s
follows the same pattern.
Complexity
Time Complexity
- Splitting the string
s
into words takesO(n)
time, wheren
is the length ofs
. - Iterating through the characters of
pattern
and words ofs
takesO(m)
time, wherem
is the length ofpattern
.
Overall time complexity is O(n + m)
.
Space Complexity
- The space complexity is
O(k)
wherek
is the number of unique characters inpattern
and unique words ins
. This is because the dictionaries will hold at mostk
key-value pairs.
Code
C++
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map pToStr;
unordered_map strToP;
vector words;
stringstream ss(s);
string word;
while (ss >> word) {
words.push_back(word);
}
if (words.size() != pattern.size()) {
return false;
}
for (int i = 0; i < pattern.size(); ++i) {
char pChar = pattern[i];
string w = words[i];
if (pToStr.count(pChar) && pToStr[pChar] != w) {
return false;
}
if (strToP.count(w) && strToP[w] != pChar) {
return false;
}
pToStr[pChar] = w;
strToP[w] = pChar;
}
return true;
}
};
Python
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
pToStr = {}
strToP = {}
words = s.split()
if len(words) != len(pattern):
return False
for pChar, word in zip(pattern, words):
# Check if there's a conflict in the mapping from pattern to word
if pChar in pToStr and pToStr[pChar] != word:
return False
# Check if there's a conflict in the mapping from word to pattern
if word in strToP and strToP[word] != pChar:
return False
pToStr[pChar] = word
strToP[word] = pChar
return True
Java
class Solution {
public boolean wordPattern(String pattern, String s) {
Map pToStr = new HashMap<>();
Map strToP = new HashMap<>();
String[] words = s.split(" ");
if (words.length != pattern.length()) {
return false;
}
for (int i = 0; i < pattern.length(); i++) {
char pChar = pattern.charAt(i);
String word = words[i];
// Check if there's a conflict in the mapping from pattern to word
if (pToStr.containsKey(pChar) && !pToStr.get(pChar).equals(word)) {
return false;
}
if (strToP.containsKey(word) && strToP.get(word) != pChar) {
return false;
}
pToStr.put(pChar, word);
strToP.put(word, pChar);
}
return true;
}
}
JavaScript
var wordPattern = function(pattern, s) {
const charToWord = new Map();
const wordToChar = new Map();
const words = s.split(' ');
let i = 0;
for (const word of words) {
if (i === pattern.length) {
return false;
}
const currentChar = pattern[i];
if (!charToWord.has(currentChar) && !wordToChar.has(word)) {
charToWord.set(currentChar, word);
wordToChar.set(word, currentChar);
} else {
if (charToWord.get(currentChar) !== word || wordToChar.get(word) !== currentChar) {
return false;
}
}
++i;
}
return i === pattern.length;
};