Problem
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
Constraints:
1 <= pattern.length <= 300
pattern
contains only lower-case English letters.1 <= s.length <= 3000
s
contains only lowercase English letters and spaces' '
.s
does not contain any leading or trailing spaces.All the words in
s
are separated by a single space.
Solution
/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function(pattern, s) {
var map = {};
var used = new Map();
var words = s.split(' ');
if (pattern.length !== words.length) return false;
for (var i = 0; i < pattern.length; i++) {
if (!map[pattern[i]]) {
if (used.has(words[i])) return false;
used.set(words[i], true);
map[pattern[i]] = words[i];
} else if (map[pattern[i]] !== words[i]) {
return false;
}
}
return true;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).