re_engine.py

gistfile1.txt

class Solution(object):
    def create_nfa(self, pattern):
        states = []

        counter = 0

        for i, value in enumerate(list(pattern)):
            if value == '*':
                continue

            state = {
                'id': counter,
                'outs': []
            }

            counter += 1

            states.append(state)

        states.append({'id': counter, 'outs': [], '_end': '_end'})

        counter = 0

        for i, value in enumerate(list(pattern)):
            if value == '*':
                continue

            if (counter != len(states)-2) and list(pattern)[i+1] == '*' :
                states[counter]['outs'].append({
                    'through': value,
                    'to': states[counter+1]
                })
                states[counter]['outs'].append({
                    'through': '',
                    'to': states[counter+1]
                })

                states[counter+1]['outs'].append({
                    'through': value,
                    'to': states[counter]
                })

            else:
                states[counter]['outs'].append({
                    'through': value,
                    'to': states[counter+1]
                })

            counter += 1
        return states

    def go_through_nfa(self, string, states):

        chars = list(string)

        flag = [False]

        self.go(states, states[0], chars, flag)

        return flag[0]

    def go(self, all_states, current_state, remained_chars, flag):
        if '_end' in current_state and len(remained_chars) == 0:
            flag[0] = True
            return

        for out in current_state['outs']:
            if out['through'] == '':
                self.go(all_states, out['to'], remained_chars[:], flag)
            else:
                if len(remained_chars) == 0:
                    return

                if out['through'] == remained_chars[0]:
                    self.go(all_states, out['to'], remained_chars[1:], flag)
    def isMatch(self, s, p):
        states = self.create_nfa(p)

        return self.go_through_nfa(s, states)