Leetcode是许多欧美IT公司招聘工程师经常使用的算法题库，学习算法最重要的是不断积累.

今天我们来看一道 "正则和字符串" 相关的题目

10. 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

问题分析：

-1. 给出一个字符串s，和一个模式p，看是否能匹配

-2.p模式中包含 普通字符, "."和 "*"

-3. "*"可以匹配之前的字符任意多次（0或者多次）

-4."."可以匹配任意单个字符

解决方案：

Solution :

1.用动态规划来存储匹配结果dp[m][n]

2.dp[m][n]表示s字符串的前m个字符可以被p前n个字符匹配

3.对"."特殊值做处理，可以匹配任意字符，所以 dp[m][n]的逻辑值由dp[m-1][n-1]的匹配结果表示

4.对"*"特殊值做处理，可以匹配前一个字符任意多次，所以 dp[m][n]的逻辑值一定可以由dp[m][n-2]的匹配结果表示,但是我们还要考虑更加特殊的情况：

c*/.*: 这种情况下，dp[m][n]可以由dp[m-1][n]或者dp[m][n]表示， 因为s的第m个字符串已经可以由p的第n-1和n两个串重复一次表示，所以dp[m][n]取决于dp[m-1][n]=dp[m-1][n-2]

总结：

这是一道 难 的题，然是有很多细节的地方会阻止你写出“简单易读”且“无逻辑错误”的代码。

本题有两个corner case需要注意：

1. 正则的理解
2. 正则串的匹配逻辑
3. 存储匹配过的结果，作为子解供后面使用
4. 动态规划的理解
5. ".*"这个特殊正则串可以匹配任意长度的字符串

关注，转发和收藏“松鼠游学”，每日更新 "Leetcode" 算法相关的面试题和解题方案并附上源码，欢迎有兴趣的小伙伴私信私聊！

@极限尤可突破，至臻亦不可止!