Dare2Solve
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
.
Split s
into Words: First, split the string s
into individual words.
Length Check: Check if the number of words matches the length of pattern
. If they do not match, return false
as it's not possible to have a bijection.
Mapping Creation: Use two dictionaries to create mappings:
pattern
to words from s
.s
to characters from pattern
.Iterate and Map: Iterate through each character in pattern
and the corresponding word in s
:
Check if the current character in pattern
is already mapped to a different word.
Check if the current word in s
is already mapped to a different character.
If there are any conflicts in the mappings, return false
.
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.
Splitting the string s
into words takes O(n)
time, where n
is the length of s
.
Iterating through the characters of pattern
and words of s
takes O(m)
time, where m
is the length of pattern
.
Overall time complexity is O(n + m)
.
O(k)
where k
is the number of unique characters in pattern
and unique words in s
. This is because the dictionaries will hold at most k
key-value pairs.class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<char, string> pToStr;
unordered_map<string, char> strToP;
vector<string> 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;
}
};
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
class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character, String> pToStr = new HashMap<>();
Map<String, Character> 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;
}
}
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;
};