## DEV Community is a community of 865,568 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Wenqi Jiang

Posted on

# 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`.

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

# Solutions

## Solution 1

### Intuition

1. compare lengths
2. build relations(map): c → w
1. map(c) ≠ w

### Code

``````public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (words.length != pattern.length()) {
return false;
}
HashMap<Character, String> map = new HashMap<>();

for (int i = 0; i < words.length; i++) {
char c = pattern.charAt(i);
String w = words[i];
if (map.containsKey(c)) {
if (!map.get(c).equals(w)) {
return false;
}
} else {
if (map.containsValue(w)) {
return false;
}
map.put(c, w);
}
}

return true;
}
``````

• Time: O(n)
• Space: O(n)