https://leetcode.com/problems/word-pattern

Pretty straightforward problem, where we need to just try to do what is asked. We need to check if our strings follow the pattern, so let us try to create this pattern and make sure that we do not have conflicts.

  1. Split our string into words, so now we have list of words.
  2. Check if length of words is equal to length of pattern and if not, immediatly return False.
  3. Now, iterate one by one elements from pattern and words: let us keep two dictionaries: one is for correspondences word -> letter and another for letter -> word. Check if we already have symb in d_symb: a. If we do not have it, but it happen that our word is already occupied, we return False, we have a conflict. b. If word is not occupied, we create two connections: one for d_symb and one for d_word. c. Finally, if symb is already in our d_symb, but word is not the one we expect to see, we return False.
  4. If we reached the end and did not return False, it means that we did not have any conflicts, so we need to return True.

Complexity: time complexity is O(n + m), where n is number of symbols in pattern and m is total number of symbols in s. Space complexity is O(k), where k is total length of all unique words.

class Solution:
    def wordPattern(self, pattern, s):
        d_symb, d_word, words = {}, {}, s.split()
        if len(words) != len(pattern): return False
        for symb, word in zip(pattern, words):
            if symb not in d_symb:
                if word in d_word: return False
                else:
                    d_symb[symb] = word
                    d_word[word] = symb
            elif d_symb[symb] != word: return False
        return True

If you like the solution, you can upvote it on leetcode discussion section: Problem 0290