python 62ms but code is a bit leng have funny


  • 0
    T
    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            if p and (p[0] == '*' or '**' in p):
                return False
    
            p_parts = []
            ps = p.split('*')
            for i in range(len(ps) - 1):
                if len(ps[i]) > 1:
                    self.split_dot(ps[i], p_parts, False)
                else:
                    self.add_to_p_parts(p_parts, '%s*' % ps[i], True)
            if ps[-1]:
                self.split_dot(ps[-1], p_parts, True)
            unchange_chars = 0
            for p_part in p_parts:
                if not p_part['changeable']:
                    unchange_chars += 1
                    if p_part['p_part'] != '.' and p_part['p_part'] not in s:
                        return False
            if len(s) < unchange_chars:
                return False
            while s:
                matched, s = self.match(s, p_parts)
                if matched is not None:
                    return matched
            for p_part in p_parts:
                if not p_part['changeable'] and not p_part['done']:
                    return False
            return True
    
        def add_to_p_parts(self, p_parts, p_part, changeable):
            if len(p_parts) > 0:
                if p_part[-1] == '*':
                    if not (p_parts[-1]['p_part'] == '.*' or p_parts[-1]['p_part'] == p_part):
                        p_parts.append({'p_part': p_part, 'changeable': changeable, 'next_sure_cs': [], 'done': False})
                    l = len(p_parts)
                    if p_part[0] == '.':
                        l -= 1
                        while l > 0:
                            if p_parts[l - 1]['p_part'][-1] == '*':
                                p_parts.pop(l - 1)
                                l -= 1
                            else:
                                break
                else:
                    p_parts.append({'p_part': p_part, 'changeable': changeable, 'next_sure_cs': [], 'done': False})
            else:
                p_parts.append({'p_part': p_part, 'changeable': changeable, 'next_sure_cs': [], 'done': False})
    
        def match(self, s, p_parts):
            s1 = s
            i = 0
            while i < len(p_parts):
                p_part = p_parts[i]
                if p_part['done']:
                    i += 1
                    continue
                if p_part['p_part'] == '.':
                    if len(s1) > 0:
                        s1 = s1[1:]
                        i += 1
                    else:
                        break
                elif p_part['p_part'][-1] == '*':
                    if p_part['next_sure_cs']:
                        c = p_part['next_sure_cs'][0]['c']
                        n = p_part['next_sure_cs'][0]['n']
                        if c:
                            index = s1[n:].find(c)
                            if index == -1:
                                return False, s
                            if p_part['p_part'][0] == '.':
                                s1 = s1[index:]
                            else:
                                for c in s1[0:index]:
                                    if c == p_part['p_part'][0]:
                                        s1 = s1[1:]
                                    else:
                                        break
                        else:
                            if len(s1) < n:
                                return False, s
                        i += 1
                    else:
                        if p_part['p_part'][0] == '.':
                            return True, s
                        else:
                            for m in s1:
                                if m == p_part['p_part'][0]:
                                    s1 = s1[1:]
                                else:
                                    break
                        i += 1
                else:
                    if p_part['p_part'] == s1[0:len(p_part['p_part'])]:
                        s1 = s1[len(p_part['p_part']):]
                        i += 1
                    else:
                        break
            if s1:
                all_done = True
                for i in range(len(p_parts)):
                    p_part = p_parts[i]
                    if not p_part['done']:
                        all_done = False
                        if p_part['p_part'] == '.':
                            s = s[1:]
                            p_part['done'] = True
                        elif p_part['p_part'][-1] == '*':
                            if p_part['next_sure_cs']:
                                s2 = s
                                done_f = False
                                for next_sure_cs in p_part['next_sure_cs']:
                                    c = next_sure_cs['c']
                                    n = next_sure_cs['n']
                                    if len(s2) < n + 1:
                                        done_f = True
                                        break
                                    index = s2[n + 1:].find(c)
                                    if index == -1:
                                        done_f = True
                                        break
                                    else:
                                        if c == '':
                                            index = n - 1
                                        if p_part['p_part'][0] == '.':
                                            s2 = s2[index + 1:]
                                            continue
                                        else:
                                            if p_part['p_part'][0] == s2[0]:
                                                c_f = False
                                                for j in s2[n + 1:index]:
                                                    if j != s2[0]:
                                                        c_f = True
                                                        break
                                                if c_f:
                                                    done_f = True
                                                break
                                            else:
                                                done_f = True
                                                break
                                if done_f:
                                    p_part['done'] = True
                                else:
                                    s = s[1:]
                                    break
                            else:
                                if p_part['p_part'][0] == '.':
                                    s = s[1:]
                                    break
                                else:
                                    if p_part['p_part'][0] == s[0]:
                                        s = s[1:]
                                        break
                                    else:
                                        p_part['done'] = True
                        else:
                            if p_part['p_part'] == s[0:len(p_part['p_part'])]:
                                s = s[len(p_part['p_part']):]
                                p_part['done'] = True
                            else:
                                return False, s
                if all_done:
                    return False, s
                return None, s
            return True, ''
    
        def split_dot(self, p_part, p_parts, is_last):
            c, n = '', 0
            next_sure_cs = []
            tmp = p_part
            if not is_last:
                tmp = p_part[:-1]
            for j in tmp:
                if j == '.':
                    if c:
                        self.add_to_p_parts(p_parts, c, False)
                        next_sure_cs.append({'c': c, 'n': n})
                        n = 0
                    self.add_to_p_parts(p_parts, '.', False)
                    n += 1
                    c = ''
                else:
                    c = '%s%s' % (c, j)
            if c:
                self.add_to_p_parts(p_parts, c, False)
                next_sure_cs.append({'c': c, 'n': n})
            if n > 0:
                next_sure_cs.append({'c': '', 'n': n})
            self.set_next_sure_char(p_parts, next_sure_cs)
            if not is_last:
                self.add_to_p_parts(p_parts, '%s*' % p_part[-1], True)
    
        def set_next_sure_char(self, p_parts, next_sure_cs):
            for p in p_parts:
                if p['changeable']:
                    p['next_sure_cs'] = p['next_sure_cs'] + next_sure_cs
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.