LeetCode 290: Word Pattern
Problem Description
Explanation
To solve this problem, we can use a HashMap to store the mapping between characters in the pattern and words in the string. We iterate through each character in the pattern and each word in the string, updating the mapping accordingly. If at any point we find a mismatch in the mapping or encounter a word that has already been assigned to a different character, we return false. If we successfully map all characters to words and vice versa, we return true.
- Time Complexity: O(n), where n is the length of the pattern or the number of words in the string.
- Space Complexity: O(n), where n is the number of unique characters in the pattern or unique words in the string.
Solutions
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (pattern.length() != words.length) {
return false;
}
Map<Character, String> charToWord = new HashMap<>();
Map<String, Character> wordToChar = new HashMap<>();
for (int i = 0; i < pattern.length(); i++) {
char c = pattern.charAt(i);
String word = words[i];
if (charToWord.containsKey(c)) {
if (!charToWord.get(c).equals(word)) {
return false;
}
} else {
charToWord.put(c, word);
}
if (wordToChar.containsKey(word)) {
if (wordToChar.get(word) != c) {
return false;
}
} else {
wordToChar.put(word, c);
}
}
return true;
}
}Related LeetCode Problems
Loading editor...