algoadvance

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

Here, follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", s = "dog dog dog dog"
Output: false

Clarifying Questions:

  1. Is the string s guaranteed to be non-empty?
    • Yes, the string s will contain at least one word.
  2. Can the pattern contain other characters apart from alphabets?
    • No, the pattern will contain only lowercase alphabets.
  3. Can the words in string s contain numbers, punctuation, etc.?
    • The words in string s will consist of lowercase alphabet characters only.
  4. Is the length of pattern equal to the number of words in s?
    • Yes, for the pattern to follow the string s, their lengths in terms of elements (letters and words) should be equal.

Strategy:

  1. Split the string into words:
    • Use in-built split function to convert string s into a list of words.
  2. Length Check:
    • Check if the length of the pattern is equal to the number of words in s. If not, return false.
  3. Mapping Creation:
    • Use dictionaries to create one-to-one mappings from pattern characters to words and from words to pattern characters.
  4. Check and Validate Mapping:
    • Iterate through each character in the pattern and each word in the list.
    • Ensure that each character in the pattern maps to exactly one word and vice versa.

Code:

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    
    if len(pattern) != len(words):
        return False
    
    char_to_word = {}
    word_to_char = {}
    
    for char, word in zip(pattern, words):
        if char in char_to_word:
            if char_to_word[char] != word:
                return False
        else:
            char_to_word[char] = word
            
        if word in word_to_char:
            if word_to_char[word] != char:
                return False
        else:
            word_to_char[word] = char
            
    return True

Time Complexity:

Therefore, the overall time complexity is O(n + k), which simplifies to O(n) since the length of pattern k and the resulting word list length are bounded by the length of the input string s.

Try our interview co-pilot at AlgoAdvance.com