[Leetcode] State Machine

Posted on | In , |

8. String to Integer (atoi)

Leetcode: https://leetcode.com/problems/string-to-integer-atoi/description/

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class StateMachine:
    def __init__(self):
        self.states = {"q0": 0, "q1": 1, "q2": 2, "qd": 3}
        self.current_state = "q0"
        self.result = 0
        self.sign = 1
        self.INT_MAX = pow(2, 31) - 1
        self.INT_MIN = -pow(2, 31)
        self.cur_char = ""
    
    def transition_to_q0(self):
        self.current_state = "q0"

    def transition_to_q1(self):
        self.current_state = "q1"
        if self.cur_char == "-":
            self.sign = -1
    
    def transition_to_q2(self):
        self.current_state = "q2"
        self.__append_number()

    def transition_to_qd(self):
        self.current_state = "qd"

    def __append_number(self):
        num = int(self.cur_char)
        if ((self.result > self.INT_MAX // 10) or 
        (self.result == self.INT_MAX // 10 and num > self.INT_MAX % 10)):
            if self.sign > 0:
                self.result = self.INT_MAX
            else:
                self.result = self.INT_MIN
                self.sign = 1
            self.transition_to_qd()
        else:
            self.result = self.result * 10 + num
        # print('here', self.result)

    def get_current_state(self):
        return self.current_state

    def proceeds(self, ch):
        self.cur_char = ch
        if self.current_state == "q0":
            if ch == " ":
                self.transition_to_q0()
            elif ch == "-" or ch == "+":
                self.transition_to_q1()
            elif ch.isdigit():
                self.transition_to_q2()
            else:
                self.transition_to_qd()
        elif self.current_state == "q1" or self.current_state == "q2":
            if ch.isdigit():
                self.transition_to_q2()
            else:
                self.transition_to_qd()

    def get_result(self):
        return self.result * self.sign

class Solution:
    def myAtoi(self, s: str) -> int:
        machine = StateMachine()
        for ch in s:
            machine.proceeds(ch)
            if machine.get_current_state() == "qd":
                return machine.get_result()
        return machine.get_result()

10. Regular Expression Matching

Leetcode: https://leetcode.com/problems/regular-expression-matching/

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class StateMachine:
    def __init__(self, p, s):
        self.p = p
        self.s = s
        self.pi = 0
        self.si = 0
        self.states = {"q0": 0, "q1": 1, "q2": 2, "qd": 3}
        self.cur_state = 0
        self.res = True

    def to_q0(self):
        # match char to char
        self.cur_state = self.states["q0"]
        self.compare_char()
        
    def compare_char(self):
        if self.p[self.pi] != self.s[self.si]:
            self.res = False
            self.to_qd()
        else:
            self.pi += 1
            self.si += 1

    def process(self, i):
        self.si = i
        if self.si >= len(self.s) or self.pi >= len(self.p):
            self.res = False
            self.to_qd()
            return

        if self.p[self.pi] == ".":
            self.to_q1()
        elif self.p[self.pi] == "*":
            self.to_q2()
        else:
            self.to_q0()
        i = self.si
        return i

    def forward(self):
        self.si += 1

    def to_q1(self):
        # match char to .
        self.cur_state = self.states["q1"]
        self.pi += 1
        self.si += 1

    def to_qd(self):
        # end machine
        self.cur_state = self.states["qd"]
    
    def get_result(self):
        return self.res

    def get_state(self):
        return self.cur_state

    def to_q2(self):
        # match char to *
        if self.pi == 0 or (self.p[self.pi - 1] != "." and self.p[self.pi - 1] != self.s[self.si]):
            # ignore
            self.pi += 1
            return

        if self.p[self.pi - 1] == ".":
            self.res = True
            self.to_qd()
            return

        if self.p[self.pi - 1] == self.s[self.si]:
            while self.si < len(self.s) and self.p[self.pi - 1] == self.s[self.si]:
                self.si += 1
            self.pi += 1
            return

        
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        machine = StateMachine(p, s)
        i = 0
        while i < len(s):
            i = machine.process(i)
            if machine.get_state() == 3:
                return machine.get_result()
        return machine.get_result()

Wildcard Matching

Valid Number’s
Detect Capital
Find and Replace Pattern
Binary Prefix Divisible By 5