一筹莫展的LeetCode10 正则表达式匹配

  1. 1. 题目
  2. 2. 解读
  3. 3. Ruby 解法
  4. 4. 后话

基本上是一筹莫展的题目，果断时间再遇到估计也还是一筹莫展。

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
[10] Regular Expression Matching  

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

* algorithms
* Hard (25.59%)
* Total Accepted:    333.7K
* Total Submissions: 1.3M
* Testcase Example:  '"aa"\n"a"'

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 preceding 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

解读

基本就是要考虑遇到.*以及*的时候。

举个例子来说，

1
2
s = "mississippi"
p = "mis*is*p*."

我们大可跳过前面不是特殊情况的完全匹配的部分，直到

1
2
s = "mi|ssissippi"
p = "mi|s*is*p*."

因为*可以匹配0到多个前面的字符s。所以，我们可以去试着递归匹配

1
2
3
4
5
6
7
8
9
s = "ssissippi"
p = "is*p*."


s = "sissippi"
p = "is*p*."

s = "issippi"
p = "is*p*."

所以基本流程是

  1. 当p长度为0，检查s是否长度为0，是的话返回true，否则返回false。
  2. 当p的长度为1， 检查s的长度是否为1，如果s长度为1，并且s和p相同亦或者p为”.”，则返回true，否则返回false。
  3. 当p[1]不为*的时候递归匹配s[1..-1] p[1..-1]。
  4. 当p[1]为*的时候，这个时候就麻烦了。因为*可以匹配0个到多个p[0]，所以我们得做一次循环，在循环中递归匹配。

Ruby 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def is_match(s, p)
  return s.length == 0  if p.length == 0
  return s.length == 1 && (s[0] == p[0] || p[0] ==".") if p.length == 1
  if p[1] != "*"
    return false if s.length == 0
    return (s[0] == p[0] || p[0] ==".") && is_match(s[1..-1], p[1..-1])
  end
  temp = s
  while s.length != 0 && (s[0] == p[0] || p[0] == ".")
    result = is_match(s[1..-1], p[2..-1])
    return true if result == true
    s = s[1..-1]
  end
  return is_match(temp, p[2..-1])
end

后话

不看答案我是真的不会，看了答案我还是懵的。

算法 leetcode
如果你觉得本文对你有帮助，请给我点赞助。