0290. Word Pattern
https://leetcode.com/problems/word-pattern
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
.
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
Example 4:
**Input:** pattern = "abba", s = "dog dog dog dog"
**Output:** false
Constraints:
1 <= pattern.length <= 300
pattern
contains only lower-case English letters.1 <= s.length <= 3000
s
contains only lower-case English letters and spaces' '
.s
does not contain any leading or trailing spaces.All the words in
s
are separated by a single space.
ac
class Solution {
public boolean wordPattern(String pattern, String str) {
// edge cases
if (str.length() < pattern.length()) return false;
String[] words = str.split(" ");
if (pattern.length() != words.length) return false;
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
for (int i = 0; i < pattern.length(); i++) {
char c = pattern.charAt(i);
if (map.containsKey(c)) {
if (!words[i].equals(map.get(c))) return false;
} else {
if (set.contains(words[i])) return false;
map.put(c, words[i]);
}
set.add(words[i]);
}
return true;
}
}
Last updated
Was this helpful?