[LeetCode]题解（python）：010-Regular Expression Matching

题目来源：

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

题意分析：

这道题目定义了两个正则表达式规则。’.’代表任意字符，’*’代表前一个字符出现任意次。输入两个字符串s，p。如果s可以被p完全匹配则返回True，否则返回False。比如’.*’可以匹配任意字符串。

题目思路：

这道题目如果直接import 正则表达式肯定是不行的，因为题目只定义了2个特殊字符，而正则表达式包括很多特殊字符，所以直接import正则表达式肯定是不行的。

从第一个字符开始搜索，对以下情况进行讨论：

①如果（s[0] == p[0]or p[0] == ‘.’）且p的第二个字符不是’*’，那么如果两个字符同时去掉第一个字符，结果不变。

②如果p[0] == ‘.’且p[1] == ‘*’那么如果存在s[i:],i >= 0被p[2:]完全匹配，则s可以被p完全匹配（s[i:]代表s字符除掉0到i下标的字符）。

③如果p[0] != ‘.’且p[1] == ‘*’，那么如果s[0] != p[0]那么如果s可以被p[2:]匹配，则s可以被p完全匹配。

④如果s[0] == p[0]那么如果存在s[i：]（i >= 0 且 s[j] == p[0] 0<= j <i）被p[2:]完全匹配，那么s可以被p完全匹配。

经过上面的分析，这道题目可以用动态规划来做。用b[i][j]来代表由s除掉0到i下标的字符能否被由p除掉0到j下标的字符完全匹配，也就是s[i:]能否被p[j:]完全匹配。根据上一段的分析可以得到：

if p[j + 1] != ‘*’

if s[i] == p[j] or p[j] == ‘.’ then b[i][j] = b[i + 1][j + 1]

else

if p[j] == ‘.’ then

if exist k (i<=k) b[k][j + 2] = true then b[i][j] = true

else b[i][j] = false

else

if exist k(i <= k)b[k][j + 2] = true and all l (0 <= l <k) s[l] = p[0] then b[i][j] =true

else b[i][j] = false

return b[0][0]

PS：由于python的二维数组初始化比较麻烦，或者是因为我对python的不熟，我选择用dictionary来处理，b[i,j]代替b[i][j].

代码（python）：

 1 class Solution(object):
 2     def isMatch(self,s, p):
 3         size1 = len(s)
 4         size2 = len(p)
 5         b = {}
 6         s1 = 0
 7         while s1 <= size1:
 8             s2 = 0
 9             while s2 <= size2:
10                 b[s1,s2] = False
11                 s2 += 1
12             s1 += 1
13         b[size1,size2] = True
14         j = size2 - 1
15         while j >= 0:
16             if p[j] == '*':
17                 b[size1,j] = False
18                 j -= 1
19                 b[size1,j] = True
20                 j -= 1
21             else:
22                 break
23         j = size2 - 1
24         while j >= 0:
25             if p[j] == '.':
26                 i = size1 - 1
27                 while i >= 0:
28                     b[i,j] = b[i + 1,j + 1]
29                     i -= 1
30             elif p[j] != '*':
31                 i = size1 - 1
32                 while i >= 0:
33                     if p[j] == s[i]:
34                         b[i,j] = b[i + 1,j + 1]
35                     else:
36                         b[i,j] = False
37                     i -= 1
38             else:
39                 i = size1 - 1
40                 if p[j - 1] == '.':
41                     while i >= 0:
42                         k = i
43                         while k <= size1:
44                             if b[k,j + 1]:
45                                 b[i,j - 1] =True
46                                 break
47                             k += 1
48                         i -= 1
49                 else:
50                     while i >= 0:
51                         k = i
52                         while k <= size1:
53                             if b[k,j + 1]:
54                                 b[i,j - 1] = True
55                                 break
56                             if k == size1:
57                                 break
58                             if p[j - 1] != s[k]:
59                                 break
60                             k +=1
61                         i -= 1
62                 j -= 1
63             j -= 1
64         return b[0,0]

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4807234.html