The Word Pattern Algorithm: How to Test if a String Follows a Pattern

Today's algorithm is the Word Pattern problem:

Given a pattern and a string str, find if str follows the same pattern.

For example, if you were given the pattern abba and the string apple pear pear apple, your function should return true since the string follows the given pattern. But, if you were given the pattern abba and the string apple pear pear orange, your function should return false since the string does not follow the pattern.

I like this algorithm because it's different from many other problems I've seen on Leetcode, but its premise does not take too long to grasp. In this post, I'll be discussing how I want to approach this problem, and then will code the solution using JavaScript.

Approaching the Word Pattern Problem

I'll be approaching this problem by creating two hashes, one for the pattern and one for the string. In the pattern hash, each of the keys will be a letter from the pattern, and the value at each key will be the string at the same index. Using an example, if the pattern were aba, and the string were apple pear apple, I'd want the pattern hash to be:

{
  "a": "apple",
  "b": "pear"
}

Essentially, in the pattern hash I want to match up each pattern element to the string element at the same index.

I also want to create a string hash, which will be based off an array version of the inputted string. In the string hash, each of the keys will be a string at an index, and its value will be the pattern at the same index. Using the same example, where pattern is aba and string is apple pear apple, I'd want the string hash to be:

{
  "apple": "a",
  "pear": "b"
}

Why do I want to use a hash? And why do I need two of them?

Hashes are useful because they enable very quick lookups. If I want to see if a key is in a hash, or find the value at that key, I can do so in constant (O(1)) time. In this problem, I want to use two hashes because there may be instances where just using the pattern hash won't catch all cases.

For example, let's say the pattern was abba and the string was dog dog dog dog. If we only had a pattern hash, it would look like this:

patternHash = {
  "a": "dog",
  "b": "dog"
}

The problem with this is that "dog" and "dog" are the same, which means the string does not vary in the same way the pattern does. If we also had a string hash, it would tell us more information. At the first index ("dog" and "a"), the string hash would include the key "dog", with a value of "a".

stringHash = {
  "dog": "a"
}

At the next index ("dog" and "b") the function would find the key "dog" in the string hash, "b" does not equal the value at that key. So, we'd know that pattern does not match the string, and we could return false.

Coding the Solution to the Word Pattern Problem

We can start the function by setting up a few variables, and doing a quick base case check. First, we'll want to make an array based on the string, which will make the rest of the function much easier to execute. To turn a string into an array, we can use the method .split(), and have it split the string on each space.

We'll want to initialize a few hashes, one for the pattern and one from the string. We also can do a quick base case check. If the length of the string array is not the same as the length of the pattern, we already know the string could not match the pattern, so we can return false.

function wordPattern(pattern, str) {
  let strArr = str.split(" ");
  let patternHash = {};
  let strHash = {};
  if (strArr.length !== pattern.length) return false;
  //...
}

Now, we'll want to set up a for loop, which will start at the 0th index and go through the length of the pattern. Inside the loop, we'll have some conditional statements. The first statement will check if the values at the keys in each hash don't match the elements we're on. Since that conditional will have quite a bit of logic, we can instead start by writing the "else" statement.

The else statement will need to establish the key-value pairs in both hashes. In the pattern hash, the keys will be the pattern at each index, and the values will be equal to the string array at that same index. In the string hash, the keys will be the string at each index, and the values will be equal to the pattern at the same index.

function wordPattern(pattern, str) {
  let strArr = str.split(" ");
  let patternHash = {};
  let strHash = {};
  if (strArr.length !== pattern.length) return false;
  for (let i = 0; i < pattern.length; i++) {
    if //...
    } else {
      patternHash[pattern[i]] = strArr[i];
      strHash[strArr[i]] = pattern[i];
    }
  }
  //...
}

Now we can move back to the "if" statement. In the if statement, we'll want to check for two cases: (1) if the pattern hash already has the pattern element at that index as a key in the hash, and the key does not have a value of the string array at that index, and (2) if the string hash already has the string array element at that index as a key in the hash, and the key does not have a value of the pattern at that index. In both of those cases, that means the string and pattern do not match, so we can return false. Because we want to check if either of those cases are true, we can use the operator "or", which is denoted with ||. In an "or" statement, if either half are true, then the condition executes.

We can write this conditional out piece by piece. We'll start with the general structure, which we can write in pseudo code.
if ((the pattern at the index is a key the pattern hash AND the value at that pattern key does not equal the string array at that index) OR (the string array at the index is a key in the string hash AND the value at that string key does not equal the pattern at that index)) THEN return false

In JavaScript, we can write this out as:
if ((pattern[i] in patternHash && patternHash[pattern[i]] !== strArr[i]) || (strArr[i] in strHash && strHash[strArr[i]] !== pattern[i])) {return false}.

function wordPattern(pattern, str) {
  let strArr = str.split(" ");
  let patternHash = {};
  let strHash = {};
  if (strArr.length !== pattern.length) return false;
  for (let i = 0; i < pattern.length; i++) {
    if (
      (pattern[i] in patternHash && patternHash[pattern[i]] !== strArr[i]) ||
      (strArr[i] in strHash && strHash[strArr[i]] !== pattern[i])
    ) {
      return false;
    } else {
      patternHash[pattern[i]] = strArr[i];
      strHash[strArr[i]] = pattern[i];
    }
  }
  //...
}

Finally, if we've checked every element of the pattern and string, and found the correct match in the corresponding hash, then we can return true. This gives us the final function:

function wordPattern(pattern, str) {
  let strArr = str.split(" ");
  let patternHash = {};
  let strHash = {};
  if (strArr.length !== pattern.length) return false;
  for (let i = 0; i < pattern.length; i++) {
    if (
      (pattern[i] in patternHash && patternHash[pattern[i]] !== strArr[i]) ||
      (strArr[i] in strHash && strHash[strArr[i]] !== pattern[i])
    ) {
      return false;
    } else {
      patternHash[pattern[i]] = strArr[i];
      strHash[strArr[i]] = pattern[i];
    }
  }
  return true;
}

--

Please let me know if you have any questions, or if you have other ways of solving this problem!

Comments

[Saloni Yadav]

a slight modification (or not). just a choice of a different DS.

var wordPattern = function(pattern, str) {
    let pat = pattern.split("");
    let s = str.split(" ");
    if (pat.length!==s.length)
        return false;

    const hash = new Map();
    const set = new Set();
    for (let i=0; i<pat.length; i++) {
        set.add(s[i]);
        if (hash.get(pat[i])) {
            if(hash.get(pat[i])!==s[i])
                return false;
        } else {
            hash.set(pat[i],s[i]);
        }
    }
    if (set.size==hash.size)
        return true;
    else 
        return false;
};