< Back

290. Word Pattern

We're given a string of characters and a string of words separated by spaces. We need to determine if
the words match the pattern provided in the string of characters.

This is similar to 205. Isomorphic Strings. We can use a dictionary to store
the mapping between the pattern characters and the words. If a mapping doesn't exist between the two,
we're good to create one. A collision notifies us that the pattern is violated by the string

An extra check has to be added, making sure the number of words is equal to the number of
characters in the pattern.

The solution is as follows:

  from collections import defaultdict

  class Solution:
      def wordPattern(self, pattern: str, s: str) -> bool:
          p_map = defaultdict(int)
          s_map = defaultdict(int)
          s_list = s.split(' ')

          if len(s_list) != len(pattern):
              return False

          for p_char, s_word in zip(pattern, s_list):
              if p_char not in p_map and s_word not in s_map:
                  p_map[p_char] = s_word
                  s_map[s_word] = p_char

              elif p_map[p_char] != s_word or s_map[s_word] != p_char:
                  return False

          return True

_ Time Complexity:

  O(n) - We iterate through all characters and words in the input.

_ Space Complexity:

  O(n) - We use a dictionary to store a mapping for all the unique words encountered.