Leetcode Regular Expression Matching

题目：Regular Expression Matching

Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

解答：

class Solution:
def isMatch(self, s, p):
m, n = len(s), len(p)
if n > 0 and p == '*': return False

s, p = s + '#' , p + '#'    # the hashtags mark the end of string/pattern

prev = [False] * (m+1)
current = [False] * (m+1)
prev[-1] = True            # end of pattern matches end of string

for i in range(n-1,-1,-1):
if True not in prev: return False     # terminate early
if p[i] == '*': continue         # ignore * and move to next char in pattern

elif p[i] != '.' and p[i+1] == '*':
current[-1] = prev[-1]
for j in range(m-1,-1,-1):
current[j] =  prev[j] or (p[i] == s[j] and current[j+1])

elif p[i] == '.' and p[i+1] == '*':
current[-1] = prev[-1]
for j in range(m-1,-1,-1):
current[j] = current[j+1] or prev[j]
elif p[i] == '.':
for j in range(m-1,-1,-1):
current[j] = prev[j+1]
else:
for j in range(m-1,-1,-1):
current[j] = prev[j+1] and p[i] == s[j]

prev = current
current = [False] * (m+1)

return prev

0 条评论

相关文章

在前面的几篇讨论里我们初步对FP有了些少了解：FP嘛，不就是F[A]吗？也是，FP就是在F[]壳子（context）内对程序的状态进行更改，也就是在F壳子（...

20570

15940

11120

22670

[C#3] 1-扩展方法

1.从DEMO开始 先看一个扩展方法的例子： 1 class Program 2 { 3 public static void Main(...

224100

JS魔法堂：再识Number type

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   本来只打算理解JS中0.1 + 0.2 == 0.300000000000000...

23950

23220

函数式编程与面向对象编程: Lambda表达式 函数柯里化 高阶函数函数式编程与面向对象编程: Lambda表达式 函数柯里化 高阶函数.md

For example, in Lisp the 'square' function can be expressed as a lambda expressi...

8520 