Sponsored
Sponsored
This approach uses two hash maps (dictionaries) to establish bijective mappings between characters in the pattern and words in the string. One map tracks the character to word mapping, while the other tracks word to character mapping. During iteration, we update or check both maps to ensure the bijection property holds.
Time Complexity: O(n + m), where n is the length of the pattern and m is the length of the string. Each space-separated word in s is checked at least once.
Space Complexity: O(n + m) for storing the mapping of characters to words and words to characters.
1import java.util.HashMap;
2
3public class Main {
4 public static boolean wordPattern(String pattern, String s) {
5 String[] words = s.split(" ");
6 if (pattern.length() != words.length) return false;
7 HashMap<Character, String> charToWord = new HashMap<>();
8 HashMap<String, Character> wordToChar = new HashMap<>();
9 for (int i = 0; i < pattern.length(); i++) {
10 char c = pattern.charAt(i);
11 String word = words[i];
12 if (charToWord.containsKey(c) && !charToWord.get(c).equals(word)) return false;
13 if (wordToChar.containsKey(word) && !wordToChar.get(word).equals(c)) return false;
14 charToWord.put(c, word);
15 wordToChar.put(word, c);
16 }
17 return true;
18 }
19
20 public static void main(String[] args) {
21 System.out.println(wordPattern("abba", "dog cat cat dog"));
22 }
23}
24This Java solution utilizes HashMaps: one for characters to words and another for words to characters. Each pattern and word are checked mutually exclusively, ensuring consistent mappings before concluding the relationship.
The index mapping approach ensures that the last seen indexes of each character in the pattern and each word from s match. By tracking their last occurrences, you can simplify identifying mismatched patterns in linear time.
Time Complexity: O(n + m), where n is the pattern length and m is s’ length.
Space Complexity: O(n + m) concerning the arrays holding the last occurring indices.
1
This solution of Java uses a single map indexMap with flexible typing that stores data for pattern's characters and string's words. Indexing both allows easier relational consistency ensuring, as identical indexes mean correctly matched mapping.