## Given problem

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
• 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.

## Analysis of this problem

Currently, our problem is about validating the mapping between each character in `pattern` string and a word in string `s` based on the concept bijection.

For example, we have string `pattern` = “abba”, string `s` = “dog cat cat fish”. The one side is that from `a` character, we have: “dog”. And the reversed side is from “dog”, we have: `a` character. But at the moment, “fish” string will be converted to `a` character. It is not correct. Our function should return `false`.

From the above points, there are two approaches for it:

• Using two Hash Maps to express the bijection concept.

• Firstly, we need to check the one side, assuming that we have a character, we need to check the corresponding string exists in the remaining Hash Map or not.

• Secondly, do the same thing but from string in `s`.

• Using only one Hash Map - from a character to a string.

The another issue happened here is that when we need to check the case of a character based on the string.

For example: pattern = “abba”, s = “dog dog dog dog”.

To solve this issue, follow the below way:

• Using two Set data structures for both `pattern` and `s`.

The other improved version for this solution is to use alphabetical array that contains 26 characters in ASCII.

## Solution 1

Below is the source code that applied for first approach in Analysis of this problem.

``````public class Solution {

public boolean wordPattern(String pattern, String s) {
Map<Character, String> charToWord = new HashMap<>();
Map<String, Character> wordToChar = new HashMap<>();

char[] chars = pattern.toCharArray();
String[] words = s.split(" ");

if (chars.length != words.length) {
return false;
}

int i = 0;
for (String word : words) {
char c = chars[i];
if (charToWord.containsKey(c) && !word.equals(charToWord.get(c))) {
return false;
} else if (wordToChar.containsKey(word) && c != wordToChar.get(word)) {
return false;
}

charToWord.put(c, word);
wordToChar.put(word, c);
++i;
}

return true;
}
}
``````

Them complexity of this solution:

• Time complexity: O(n) with n is the length of pattern.
• Space complexity: O(n)

## Solution 2

Below is the source code that applied for second approach in Analysis of this problem.

``````class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character, String> mapper = new HashMap<>();
Character[] characters = pattern.chars()
.mapToObj(c -> (char) c)
.toArray(Character[]::new);
String[] words = s.split(" ");

if (invalidLength(characters, words)) {
return false;
}

int commonLength = characters.length;
for (int i = 0; i < commonLength; ++i) {
char c = characters[i];
String word = words[i];

if (mapper.containsKey(c)) {
String tmp = mapper.get(c);
if (!word.equals(tmp)) {
return false;
}
}

mapper.put(c, word);
}

return true;
}

private boolean invalidLength(Character[] charsPattern, String[] words) {
if (charsPattern.length != words.length) {
return true;
}

Set<String> wordsSet = new HashSet<>(Arrays.asList(words));
}
}
``````

Them complexity of this solution:

• Time complexity: O(n) with n is the length of pattern.
• Space complexity: O(n)

Then, to improve the above solution, we will not use two Set data structures for checking lengths of both strings.

``````public class Solution {

public boolean wordPatternV2(String pattern, String s) {
Map<Character, String> charToWord = new HashMap<>();
char[] chars = pattern.toCharArray();
String[] words = s.split("\\s+");

if (words.length != pattern.length()) {
return false;
}

int i = 0;
for (char c : chars) {
if (charToWord.containsKey(c)) {
if (!charToWord.get(c).equals(words[i++])) {
return false;
}
} else {
if (charToWord.containsValue(words[i])) {
return false;
}

charToWord.put(c, words[i++]);
}
}

return true;
}
}
``````

Them complexity of this solution:

• Time complexity: O(n^2) with n is the length of pattern.

Due to using the `containsValue()` method of HashMap, it can run in `O(n)` complexity.

• Space complexity: O(n)

To further optimize our current solution, we will use the alphabetical array.

``````public class Solution {

public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (words.length != pattern.length()) {
return false;
}

String[] alphabets = new String[26];
for (int i = 0; i < words.length; i++) {
alphabets[pattern.charAt(i) - 'a'] = words[i];
}

for (int i = 0; i < words.length; i++) {
if (!alphabets[pattern.charAt(i) - 'a'].equals(words[i])) {
return false;
}
}

for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
if (alphabets[i] != null && alphabets[j] != null && alphabets[i].equals(alphabets[j])) {
return false;
}
}
}

return true;
}
}
``````

## Wrapping up

Refer:

290. Word Pattern