135 lines
3.7 KiB
Markdown
135 lines
3.7 KiB
Markdown
## 每日一题 - Regular Expression Matching
|
||
|
||
### 信息卡片
|
||
|
||
- 时间：2019-06-09
|
||
- 题目链接：https://leetcode.com/problems/regular-expression-matching/
|
||
- tag：`String` `Dynamic Programming` `Backtracking`
|
||
|
||
### 题目描述
|
||
|
||
```
|
||
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
|
||
|
||
```
|
||
|
||
本题要求判断给出的字符串和对应的正则是否匹配，匹配返回true，否则返回false。
|
||
|
||
本题光从解题来看，可以使用api作弊，比如用Java字符串的matches方法就可以一步过这道题，本题老老实实做的话，就需要用到动态规划。基本思路是考察s和p任意从头到两个字符之间的匹配程度，有点像编辑距离那道题。
|
||
|
||
### 参考答案
|
||
|
||
```java
|
||
class Solution {
|
||
public boolean isMatch(String s, String p) {
|
||
if (s == null || p == null) return false;
|
||
|
||
// dp[i][j]代表s的前i位字符和p的前j位字符的匹配程度
|
||
// dp[1][2]代表s的第一个字符和p的前两个字符的匹配
|
||
// 如果s的第i个字符和p的第j个相等或者j为.那么di[i][j]的匹配程度取决于dp[i - 1][j - 1]
|
||
// 如果p的第j个字符为*，那么就要考虑*匹配0个，1个，n个s的第i个字符的情况，以及根本匹配不了的情况
|
||
// 根本匹配不了的意思是指p的j - 1个字符和s的第i个字符不相同，此时的匹配情况是dp[i][j] = dp[i][j - 2]
|
||
// 然后是p的第j - 1个字符是.或者和s的i个字符相同的情况，此时可以匹配0 1 个n个s的第i个字符
|
||
// 0个: dp[i][j] = dp[i][j - 2]
|
||
// 1个: dp[i][j] = dp[i - 1][j - 1]
|
||
// n个: dp[i][j] = dp[i - 1][j]
|
||
// n个的最不好理解，可以按照下面的想
|
||
// 我能匹配你n个，我肯定匹配了你前面的n-1个，也就是dp[i - 1][j]
|
||
// 最后的结果是dp[s.length()][p.length()]
|
||
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
|
||
|
||
dp[0][0] = true;
|
||
|
||
for (int j = 2; j <= p.length(); j++) {
|
||
if (p.charAt(j - 1) == '*' && dp[0][j - 2]) dp[0][j] = true;
|
||
}
|
||
|
||
for (int i = 1; i <= s.length(); i++) {
|
||
for (int j = 1; j <= p.length(); j++) {
|
||
if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
|
||
dp[i][j] = dp[i - 1][j - 1];
|
||
} else if (p.charAt(j - 1) == '*') {
|
||
if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
|
||
dp[i][j] = dp[i][j - 2];
|
||
} else {
|
||
dp[i][j] = (dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
return dp[s.length()][p.length()];
|
||
}
|
||
}
|
||
|
||
```
|
||
### 其他优秀解答
|
||
```
|
||
暂无
|
||
```
|