# LeetCode Notes: Word Pattern

## Question

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.

## Solution

Analysis:

The general idea is to divide the string into arrays and then traverse the processing. Here we use a new method-regular expressions.

1. Because the string `s` is a space-separated English word, it is very regular. You can use regular expressions to parse the `s` string and match each individual word. In the callback function of the `replace` method, each word is processed.
2. We construct a map to record each word and the corresponding position of the `pattern` letter. We add a prefix to the word to prevent letter conflicts in `pattern`, because a word may also be a letter.
3. For each word processed, we need to judge if the word or `pattern` letter has appeared before, whether the current corresponding value is consistent with the last time it appeared, and once it is inconsistent, the rule is not followed. Here you need to judge the word and the `pattern` letter at the same time to ensure a true two-way connection.
4. Finally deal with a special case, if there is only one word, because there is not enough comparison, we cannot find the problem inside the `replace` callback function, So at the end, make sure that the lengths of `s` and `pattern` need to be the same.

Code:

``````/**
* @param {string} pattern
* @param {string} s
* @return {boolean}
*/
var wordPattern = function (pattern, s) {
var count = 0;
var map = new Map();
var flag = true;
var rr = s.replace(/\b(?=\S)(\S*)/g, function (\$0) {
// Follow the replace match of s to get the corresponding pattern letter
let p = pattern[count++];
// For return value
let r = p + \$0;
// 1. Both p and "\$" + \$0 need to be judged
// get(p):'aaaa':'dog cat cat dog'
// get('\$' + \$0):'abba':'dog dog dog dog'
// 2. Add a prefix'\$' + \$0 to solve 'abc':'c b a'
if (
(map.has(p) && map.get(p) !== \$0) ||
(map.has("\$" + \$0) && map.get("\$" + \$0) !== p)
) {
flag = false;
} else {
map.set(p, \$0);
map.set("\$" + \$0, p);
}

return r;
});
// 3. The length of pattern must be equal to the length of s, solve 'jquery':'jquery'
return flag && rr.split(" ").length === pattern.length;
};
``````