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. Specifically:
Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
The bijection can be established as:
'a' maps to "dog".
'b' maps to "cat".
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.
My Solution
We can solve this problem with two HashMaps. One HashMap maps each character in pattern to a word in s. The other HashMap maps each word in s to a character in pattern. First off, if the number of words in s does not equal the number of characters in pattern, we return false. Then we iterate through the characters in pattern and check both HashMaps to make sure we are not doing any double mapping. If not we just update the two HashMaps with the new mappings.
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
Map<Character,String> char_to_word = new HashMap<>();
Map<String,Character> word_to_char = new HashMap<>();
int n = pattern.length();
if (n != words.length) {
return false;
}
for (int i = 0; i < n; i++) {
char c = pattern.charAt(i);
if (char_to_word.containsKey(c) && !char_to_word.get(c).equals(words[i])) {
return false;
}
if (word_to_char.containsKey(words[i]) && word_to_char.get(words[i]) != c) {
return false;
}
char_to_word.put(c, words[i]);
word_to_char.put(words[i], c);
}
return true;
}
}