Leetcode 290. Word Pattern

Problem

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.

Algorithm

Use the dictionary to save the two list.

Code

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        plen = len(pattern)
        dict_p = dict()
        dict_s = dict()
        word = ""
        index = 0
        for c in s:
            if c >= 'a' and c <= 'z':
                word += c
            else:
                if index >= plen:
                    return False
                pi = pattern[index]
                if index < plen and not pi in dict_p and not word in dict_s:
                    dict_p[pi] = word
                    dict_s[word] = pi
                elif pi in dict_p and dict_p[pi] != word or word in dict_s and dict_s[word] != pi:
                    return False
                index += 1
                word = ""
        
        if index >= plen:
            return False
        pi = pattern[index]
        if index < plen and not pi in dict_p and not word in dict_s:
            dict_p[pi] = word
            dict_s[word] = pi
        elif pi in dict_p and dict_p[pi] != word or word in dict_s and dict_s[word] != pi:
            return False

        for i in range(index, plen):
            if not pattern[i] in dict_p:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35