loading...

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

alisabaj profile image Alisa Bajramovic ・5 min read

Algorithm of the Day (34 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 32 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time

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!

Algorithm of the Day (34 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 32 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time

Posted on Jun 29 by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide