PROBLEM 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.
SOLUTION
This problem is similar to Isomorphic Strings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public boolean wordPattern(String pattern, String s) {
// Two HashMaps to store the mappings between characters in pattern and words in s,
// in both directions (pattern to word and word to pattern).
Map<Character, String> psMap = new HashMap<>(); // pattern-to-word mapping
Map<String, Character> spMap = new HashMap<>(); // word-to-pattern mapping
// Split the input string s into individual words based on spaces.
String[] words = s.split(" ");
// If the number of words in s does not match the length of the pattern,
// then s cannot follow the same pattern, and we return false.
if (words.length != pattern.length())
return false;
// Iterate through each character in pattern and its corresponding word in s.
for (int i = 0; i < words.length; i++) {
Character p = pattern.charAt(i);
String word = words[i];
// Check if the pattern-to-word mapping is consistent.
// If the character p is already mapped to a different word than the current word,
// then s does not follow the same pattern, and we return false.
if (psMap.containsKey(p) && !psMap.get(p).equals(word))
return false;
// Check if the word-to-pattern mapping is consistent.
// If the word is already mapped to a different character than the current character p,
// then s does not follow the same pattern, and we return false.
if (spMap.containsKey(word) && spMap.get(word) != p)
return false;
// Update the mappings in both psMap and spMap.
psMap.put(p, word); // Map character p to the current word.
spMap.put(word, p); // Map the current word to character p.
}
return true;
}
}