原题说明

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

解题思路

• 如果`j + 1``*`的话，我们可以从`(i, j)`走到`(i, j + 2)`代表我们跳过这个pattern, 或者从`(i, j)`走到`(i + 1, j)`代表我们选择匹配这个字符
• 如果不是`*`的话，那么我们直接从`(i, j)`走到`(i + 1, j + 1)`. 这意味着我们匹配了`(i, j)`

• 如果`j + 1``*`的话, 我们可以从`(i, j)`走到`(i, j + 2)`代表我们跳过这个pattern
• 如果不是, 那么说明必然不匹配, `(i, j)`的状态是`False`
终结状态就是`s``p`都用完, 也就是走到`(S + 1, P + 1)`的时候.
如果`p`用完了, 但是`s`还有剩余, 那么显然不匹配.
如果`s`用完了, `p`还有剩余, 那么只有当接下来都是有`*`的pattern的时候才匹配.

归纳总结

------ 关注公众号：猩猩的乐园 ------