0. 前言
LeetCode的一道算法题:正则字符串匹配。涉及了比较复杂的递归和动态规划算法,特此记录。
1. 题目
regular-expression-matching(正则字符串匹配)
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).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, ‘.‘) → true(这里的p是一个点和一个星号)
isMatch(“ab”, “.“) → true(同上)
isMatch(“aab”, “ca*b”) → true(c星号a星号b)
2. 分类递归
2.1 思路
最直观的做法就是根据s和p的情况进行分类匹配,
然后递归判断,每次递归视情况匹配p的前1或2个字符。
为使分类清晰,这里根据p字符串的长度进行分类:
- 当p.length = 0,返回s.isEmpty()
- 当p.length = 1(说明没有”*”),判断s时候也是长度为1且当前字符能够匹配
- 当p.length > 1,且p[1] != “*”(不含星号的情况)
若s为空,返回false,否则就是单一字符进行匹配,递归判断s和p的下一个字符。 - 当p.length > 1,且p[1] = “*”(含星号的情况),
则应该把可能重复的s字符逐一匹配然后去掉,使用一个循环,
由于星号的特性,要考虑到当前p的前两个字符可能匹配不到任何的s,
所以要先判断下isMatch(s, p.substring(2)),即当前p的前两个字符不进行任何匹配。
然后再是逐一判断s[0]与p[0]是否相等,是则s取下一字符,否则结束循环。
循环结束后,说明p的前两个字符已经匹配完毕,p取后面的字符。
2.2 实现
1 | private static boolean isMatch_recursion(String s, String p) { |
2.3 另一实现
当模式中的第二个字符不是“*”时:
1、如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。
2、如果 字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。
而当模式中的第二个字符是“*”时:
如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。如果字符串第一个字符跟模式第一个字符匹配,可以有3种匹配方式:
1、模式后移2字符,相当于x*被忽略;
2、字符串后移1字符,模式后移2字符;
3、字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;
这里需要注意的是:Java里,要时刻检验数组是否越界。
来源:牛客网
1 | public boolean match(String s, String p) { |
3. 动态规划
3.1 思路
设dp[i][j]为字符串s前i个字符与正则式p前j个字符的匹配结果,记m = s.length(),n = p.length(),因此所求最终结果为dp[m][n]。
初始状态:
显然,dp[0][0] = true,
第一行表示s = “” 去匹配全部p,只需要注意’*‘。当p[i - 1] = ‘*’ && dp[0][i - 1] = true时dp[0][i + 1] = true,
第一列表示p = “” 去匹配全部s,显然全为false。
状态转移方程:
- 如果 p[j] == str[i] || pattern[j] == ‘.’, 此时dp[i][j] = dp[i-1][j-1];
- 如果 p[j] == ‘*’
分两种情况:- 1: 如果p[j-1] != str[i] && p[j-1] != ‘.’, 此时dp[i][j] = dp[i][j-2] //*前面字符匹配0次
- 2: 如果p[j-1] == str[i] || p[j-1] == ‘.’
此时dp[i][j] = dp[i][j-2] // *前面字符匹配0次
或者 dp[i][j] = dp[i][j-1] // *前面字符匹配1次
或者 dp[i][j] = dp[i-1][j] // *前面字符匹配多次
示例(0、1表示匹配失败、成功):
s\p | “” | a | * | b | * |
---|---|---|---|---|---|
“” | 1 | 0 | 1 | 0 | 1 |
a | 0 | 1 | 1 | 0 | 1 |
a | 0 | 0 | 1 | 0 | 1 |
a | 0 | 0 | 1 | 0 | 1 |
a | 0 | 0 | 1 | 0 | 1 |
3.2 实现
1 | private static boolean isMatch_dp(String s, String p) { |
Copyright © 2018, GDUT CSCW back-end Kanarien, All Rights Reserved