Go to “Word Pattern (#290)” on Leetcode ↗

I’ve seen this problem in a couple of interviews. In this problem, different letters in the pattern must correspond to different words (for example, abba doesn’t match dog dog dog dog because a and b can’t both refer to dog). One variant of this problem is to allow that. In this problem, the pattern must fully match str; another variant is for the match to happen anywhere within str. That variant is a bit harder, and it becomes even harder if str doesn’t contain spaces separating words.

Fortunately, we have an easy version of this problem here.

“Bijection” in the problem statement is a fancy way of saying there’s a one-to-one mapping between elements in two sets. In the case of this problem, that means there’s a one-to-one mapping between the letters in pattern and words in str:

  • There are no unpaired letters or words.
  • The same letter can’t refer to different words, and
  • The same word can’t be represented by different letters

Solution 1: Hashify

We split pattern on an empty string to get an array of its letters ('abc'.split('') returns ['a', 'b', 'c']), and we split str on a single space to get an array of its words. Then, using the pattern to guide us, we go through the letters in the pattern and its corresponding word and check if they match. Along the way, we return false if any of the bijection conditions no longer appear to be true.

def word_pattern(pattern, str)
  pattern_letters = pattern.split('')
  str_words = str.split(' ')
  return false unless pattern_letters.length == str_words.length
  pattern_hash = {}
  pattern_letters.each_with_index do |letter, index|
    word = str_words[index]
    return false if pattern_hash[letter] && pattern_hash[letter] != word
    pattern_hash[letter] = word
  end
  return false if pattern_hash.values.length != pattern_hash.values.uniq.length
  true
end

Inside the loop, we set pattern_hash[letter] = word — that is, we’re building a hash of letters → words.

We return false unless the number of letters match the number of words, because if they don’t match, that means there will be unpaired letters or words.

We return false if pattern_hash[letter] exists and isn’t the same as the current word, because this would mean that the same letter is referring to different words.

We return false if the number of words in pattern_hash (represented by pattern_hash.values) is different from the unique number of words. This would only happen if the same word is appearing for more than one letter.