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.
- code
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] l = s.split(" ");
if (l.length != pattern.length()) return false;
Map<Character, String> m = new HashMap<>();
Set<String> v = new HashSet<>();
for (int i = 0; i < pattern.length(); i++){
if (m.containsKey(pattern.charAt(i))){
if (!m.get(pattern.charAt(i)).equals(l[i])) return false;
}else{
if (v.contains(l[i])) return false;
m.put(pattern.charAt(i), l[i]);
v.add(l[i]);
}
}
return true;
}
}
- code
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
s = s.split(" ")
if len(pattern) != len(s): return False
m = {}
visited_word = set()
for i in range(len(pattern)):
if pattern[i] not in m:
m[pattern[i]] = s[i]
if s[i] in visited_word: return False
visited_word.add(s[i])
else:
if m[pattern[i]] != s[i]: return False
return True