Word Follows Pattern

TIP101 Unit 3 Session 2 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Will the patterns always be only "a" and "b"?
  • No. Your solution should work for any pattern string.
• Can two different pattern letters map to the same word?
  • No. The mapping must be one-to-one in both directions: each letter maps to exactly one word, and each word maps back to exactly one letter. For example, pattern "ab" with "dog dog" does not follow the pattern.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Create a map of pattern letters -> words and a second map of words -> pattern letters, and if there is ever an inconsistency in either direction, return False.

1) Split the input string into a list of words
2) If the # of words is different from pattern length, return False
3) Create two empty dicts: one mapping pattern chars to words,
   and one mapping words back to pattern chars
4) For each index, word in the words list
  a) Get the pattern char at that index
  b) Is the char already in the char map?
    i) If not, add char -> word to the char map
   ii) Otherwise, if char map[char] != word, return False
  c) Is the word already in the word map?
    i) If not, add word -> char to the word map
   ii) Otherwise, if word map[word] != char, return False
5) If we go through all words and don't break the
   pattern, return True

I-mplement

def wordPattern(pattern, s):
    words = s.split()
    if len(pattern) != len(words):
        return False
    
    char_to_word = {}
    word_to_char = {}
    for index, word in enumerate(words):
        p_char = pattern[index]
        # Did we already use this char for another word?
        if p_char not in char_to_word:
            char_to_word[p_char] = word
        elif char_to_word[p_char] != word:
            return False
        # Did we already use this word for another char?
        if word not in word_to_char:
            word_to_char[word] = p_char
        elif word_to_char[word] != p_char:
            return False

    # We couldn't find any mis-matches
    return True