LeetCode Notes: Word Pattern

#leetcode

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;
};

Reference

Comments