String Pattern

Algorithms
string
Catalogue
  1. 1. 290. Word Pattern
  2. 2. 291. Word Pattern II
  3. 3. 809. Expressive Words
  4. 4. 890. Find and Replace Pattern

290. Word Pattern

  • Why we need Two HashTable?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def wordPattern(self, pattern, str):
        words = str.split()
        m, n = len(pattern), len(words)
        if m != n:
            return False
        dic = {}
        used = set()
        for i in range(m):
            if pattern[i] not in dic:
                if words[i] in used:
                    return False
                dic[pattern[i]] = words[i]
                used.add(words[i])
            else:
                if dic[pattern[i]] != words[i]:
                    return False
        return True

291. Word Pattern II

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
class Solution:
    def wordPatternMatch(self, pattern, str):
        return self.isMatch(pattern, str, {}, set())

    def isMatch(self, pattern, s, dic, used):
        if not pattern and not s:
            return True
        elif not pattern or not s:
            return False

        ch = pattern[0]
        if ch in dic:
            word = dic[ch]
            n = len(word)
            if word == s[:n]:
                return self.isMatch(pattern[1:], s[n:], dic, used)
            else:
                return False
        else:
            for i in range(len(s)):
                if s[:i+1] in used:
                    continue
                dic[ch] = s[:i+1]
                used.add(s[:i+1])
                if self.isMatch(pattern[1:], s[i+1:], dic, used):
                    return True
                used.remove(s[:i+1])
                del dic[ch]
            return False

809. Expressive Words

  • pairs <character, counter>
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
class Solution:
    def expressiveWords(self, S, words):
        pairs = []
        for i in range(len(S)):
            if not pairs or S[i] != pairs[-1][0]:
                pairs.append([S[i], 1])
            else:
                pairs[-1][1] += 1

        cnt = 0
        for word in words:
            if self.isExtended(pairs, word):
                cnt += 1
        return cnt

    def isExtended(self, pairs, word):
        i = 0
        for j in range(len(pairs)):
            ch, cnt = pairs[j]
            if cnt < 3:
                while cnt:
                    if i >= len(word) or ch != word[i]:
                        return False
                    cnt -= 1
                    i += 1
            else:
                ncnt = 0
                while i < len(word) and word[i] == ch:
                    i += 1
                    ncnt += 1

                if ncnt == 0 or ncnt > cnt:
                    return False
        return i == len(word)

890. Find and Replace Pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        res = []
        for word in words:
            if self.isMatched(word, pattern):
                res.append(word)
        return res

    def isMatched(self, word, pattern):
        mapw = {}
        mapp = {}
        for ch1, ch2 in zip(word, pattern):
            if ch1 not in mapw:
                mapw[ch1] = ch2
            else:
                if mapw[ch1] != ch2:
                    return False

            if ch2 not in mapp:
                mapp[ch2] = ch1
            else:
                if mapp[ch2] != ch1:
                    return False
        return True
Share