算法w2——Regular Expression Matching（leetcode 10）

题目：Regular ExPRession Matching（leetcode 10）

链接：https://leetcode.com/problemset/algorithms/

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.'*' Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true解题思路：
解这道题最大的难度在于*号，首先需要理解*号的意义，它是指*号前面的那个字符可以出现0次或多次，根据这个规则，我们需要对正则表达式做一下处理，将*号与他之前的一个字符看成同一个字符，这个思想很关键。
在做完*号的处理后，匹配时首先判断是否有*号，有*号的话匹配路程需要做一次分支，即继续留在正则表达式的该字符还是跳到下一个字符，这相当于一个二叉树，有*号就分支。判断完*号之后只需判断是否字符匹配，比较简单。其中会遇到很多意想不到的情况，把所有情况考虑完全即可。
在程序的编写上我使用了最愚蠢粗暴但也是逻辑最简单的方法，即通过if判断把所有情况考虑完就accept了。但是如果要追求时间效率来说，使用递归或者栈（深度优先）或者队列（广度优先）的方法实现程序结构会更加明显，效率也可能更高，这个是我做完这题后才思考到的。
代码如下：
class Solution(object):    def isMatch(self, s, p):        """        :type s: str        :type p: str        :rtype: bool        """        char_list = []        for i in range(0, len(p)):            if p[i] != '*':                char_list.append(p[i])            else:                char_list[-1] += p[i]        possible_ans = [['', 0]]        while True:            del_list = []            possible_ans_diff = []            for i in range(0 ,len(possible_ans)):                if possible_ans[i] not in possible_ans_diff:                    possible_ans_diff.append(possible_ans[i])            possible_ans = possible_ans_diff            print possible_ans            for i in range(0, len(possible_ans)):                ans_0 = possible_ans[i][0]                ans_1 = possible_ans[i][1]                if ans_1 == len(char_list) and ans_0 != s:                    del_list.append(i)                    continue                if len(ans_0) == len(s):                    flag = 0                    for j in char_list[ans_1:]:                        if j[-1] != '*':                            del_list.append(i)                            flag = 1                            break                    if flag == 1:                        continue                    else:                        return True                else:                    char = s[len(ans_0)]                if char_list[ans_1][-1] == char or char_list[ans_1][-1] == '.':                    possible_ans[i][0] += char                    possible_ans[i][1] += 1                elif char_list[ans_1][-1] == '*':                    if char_list[ans_1][0] == char or char_list[ans_1][0] == '.':                        possible_ans[i][0] += char                        possible_ans.append([ans_0+char, ans_1+1])                        possible_ans.append([ans_0, ans_1+1])                    else:                        possible_ans[i][1] += 1                else:                    del_list.append(i)            del_list.sort(reverse=True)            for d in del_list:                del possible_ans[d]            if len(possible_ans) == 0:                return False            for ans in possible_ans:                if ans[0] == s and ans[1] == len(char_list):                    return Trueif __name__ == '__main__':    sol = Solution()    print sol.isMatch('bbbba', '.*a*a')