010. 正则表达式匹配 | Leetcode题解
16lz
2021-01-22
题目描述:
给定一个字符串( s
) 和一个字符模式( p
)。实现支持 '.'
和 '*'
的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个 字符串( s
) ,而不是部分字符串。
说明:
s
可能为空,且只包含从a-z
的小写字母。p
可能为空,且只包含从a-z
的小写字母,以及字符.
和*
。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释:'*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例3:
输入:
s = "ab"
p = ".*"
输出: true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释:'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
提示:
0 <= s.length <= 20
0 <= p.length <= 30
s
可能为空,且只包含从a-z
的小写字母。p
可能为空,且只包含从a-z
的小写字母,以及字符.
和*
。- 保证每次出现字符
*
时,前面都匹配到有效的字符
难度:
- 难度:困难
- 支持语言:JavaScript、Java、Python、C++
相关标签
- 字符串
- 动态规划
- 回溯算法
相关企业
- 阿里
- 京东
- 腾讯
- 字节
复杂度分析
- 时间复杂度:O(mn)O(mn),其中 mm 和 nn 分别是字符串 ss 和 pp 的长度。我们需要计算出所有的状态,并且每个状态在进行转移时的时间复杂度为 O(1)O(1)。
- 空间复杂度:O(mn)O(mn),即为存储所有状态使用的空间。
思路 1(javascript):
动态规划
,dp[i][j]
代表到索引[0,i]
的p
是否能被索引[0,j]
的s
匹配。
如果p[i]===s[j] || p[i]==='.'
,说明它们匹配,dp[i][j]=dp[i-1][j-1]
。
如果不匹配,但是p[i]==='*'
,
- 如果
p
的前一个能和当前s
匹配并且dp[i][j-1]===true
,说明*
可以延长上一个的p
来匹配当前的s
; - 如果上面条件不符合,但是
dp[i-2][j]===true
,也就是说前2个的p
能和当前s
匹配,那么*
可以作为数量0
,相当与忽略前一个p
。
思路 2:
- p[j−1]p[j - 1]p[j−1]为普通字符,若s[i−1]==p[j−1]s[i - 1] == p[j - 1]s[i−1]==p[j−1],则dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i−1][j−1],否则匹配失败
- p[j−1]p[j - 1]p[j−1]为
'.'
,则dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i−1][j−1] - p[j−1]p[j - 1]p[j−1]为
'*'
:- (1)不看,则dp[i][j]=dp[i][j−2]dp[i][j] = dp[i][j - 2]dp[i][j]=dp[i][j−2]
- (2)看,则dp[i][j]=dp[i−1][j]dp[i][j] = dp[i - 1][j]dp[i][j]=dp[i−1][j]
思路 3 py:
- 先判断s和p的第一个字符是否匹配
- 处理p[1]为
*
号的情况:匹配0个或多个字符 - 处理
.
号的情况:匹配一个字符
思路 4 C++:
- 用指针的方法:
- 当
*s
和*p
都空时,返回true
- 当
*s
不空,*p
空时,返回false
- 当
*s
空,*p
非空时,不一定,eg: p = "a*a*a*a*"
,最后一个*
可以表示a
出现0
次 '*'
是关键因素,所以我们这里分*(p + 1) == '*'
和*(p + 1) != '*'
*(p + 1) != '*'
,这种情况直接匹配当前字符,如果匹配成果,继续匹配下一个,匹配失败则返回false
, 所谓的匹配成功(1)相同字符(2)*p = '.'
和*s != '\0'
*(p + 1) == '*'
,'*'可以表示0个及0个以上的字符
:
- 匹配:(1)
s
不动,p
后移两位(2)s
后移一位,p
不动 - 不匹配:
s
不动,p
后移两位,跳过符号'*'
代码
JavaScript 实现
/**
* @来源:Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let pLen=p.length,sLen=s.length
let dp=Array(pLen+1).fill().map(()=>Array(sLen+1).fill(false))
for(let i=0;i<pLen+1;i++){
for(let j=0;j<sLen+1;j++){
if(i===0 && j===0){
dp[i][j]=true
}else if(p[i-1]==="*" && j===0){
dp[i][j]=dp[i-2][j]
}
}
}
for(let i=1;i<pLen+1;i++){
for(let j=1;j<sLen+1;j++){
let r=i-1,c=j-1
if(p[r]===s[c] || p[r]==='.'){
dp[i][j]=dp[i-1][j-1]
}else if(p[r]==="*"){
if(((p[r-1]===s[c] || p[r-1]===".") && dp[i][j-1]) || dp[i-2][j])
dp[i][j]=true
}
}
}
return dp[pLen][sLen]
};
/**
作者:arrowing
链接:https://leetcode-cn.com/problems/regular-expression-matching/solution/javascript-jie-fa-fei-zheng-ze-chao-yue-99-de-ti-j/
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
if (p.indexOf('*') === -1) { // 没有星号
return isEqual(s, p)
} else { // 有星号
let splitArr = []
let sIndex = 0
let index
// 第 1 步:将匹配模式串(p)格式化为有序的匹配串数组;
while ((index = p.indexOf('*', sIndex)) > -1) {
if (sIndex < index - 1) {
splitArr.push( p.substring(sIndex, index - 1) )
}
splitArr.push( p[index - 1] + '*' )
sIndex = index + 1
}
if (sIndex < p.length) {
splitArr.push( p.substring(sIndex) )
}
// 第 2 步:将头尾不带星号的内容优先匹配(因为这部分内容必须完全匹配);
// 先去除头部
let headStr = splitArr[0]
if (headStr[1] !== '*') {
if ( isEqual(s.substring(0, headStr.length), headStr) ) {
s = s.substring(headStr.length)
splitArr.shift()
} else {
return false
}
}
// 再去除尾部
let tailStr = splitArr[splitArr.length - 1]
if (tailStr[1] !== '*') {
if ( isEqual(s.substring(s.length - tailStr.length), tailStr) ) {
s = s.substring(0, s.length - tailStr.length)
splitArr.pop()
} else {
return false
}
}
return recursionMatch(s, splitArr)
}
};
/**
* @param {string} s
* @param {string[]} arr
* @return {boolean}
*/
function recursionMatch (s, arr) {
let item
let index = -1
for (let i = 0; i < arr.length; i++) {
item = arr[i]
// 第 3 步
if (item[1] !== '*') { // 先处理不带星号的,因为必须要匹配到
// 第 4 步
if (item.indexOf('.') > -1) { // 不带星号,但是带点号
let sLen = s.length
let pLen = item.length
if (pLen > s.length) {
return false
} else {
let j = 0
while (j < sLen) {
if (isEqual(s.substring(j, j + pLen), item)) {
let result
if (j > 0) { // 匹配了,先消耗匹配值的左边内容
result = costStarArr(s.substring(0, j), arr.slice(0, i))
}
if (j === 0 || result === true) { // 消耗匹配值的剩余内容
let leftStr = s.substring(j + pLen)
let leftArr = arr.slice(i + 1)
result = recursionMatch(leftStr, leftArr)
}
if (result === true) {
return true
}
}
j++
}
// 带点号的内容匹配不到
return false
}
}
// 第 5 步
while ((index = s.indexOf(item, index + 1)) > -1) { // 各种可能性都进行匹配
// console.log('recursionMatch:', s, arr, i, index)
let result = costStarArr(s.substring(0, index), arr.slice(0, i)) // 匹配了,先消耗匹配值的左边内容
// 第 6 步
if (result === true) { // 左边内容成功消耗,看剩余内容是否能匹配
let leftStr = s.substring(index + 1)
let leftArr = arr.slice(i + 1)
if (leftStr.length) {
if (leftArr.length) {
let result = recursionMatch(leftStr, leftArr)
if (result === true) { // 剩余内容也匹配到了
return true
}
} else {
return false
}
// 第 8 步
} else { // 剩余可匹配内容为空
if (leftArr.length) { // 仍有可匹配数组
return leftArr.every(item => item[1] === '*')
}
return true
}
}
}
// 第 7 步
// 不带星号的内容匹配不到
return false
}
}
return costStarArr(s, arr)
}
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
function isEqual (s, p) {
if (s.length !== p.length) {
return false
}
let i = 0
while ( i < s.length && (s[i] === p[i] || p[i] === '.') ) {
i++
}
return s.length === i
}
/**
* @param {string} s
* @param {string[]} starArr
* @return {boolean}
*/
function costStarArr (s, starArr) {
if (s.length === 0) return true
while (starArr.length) {
let tmp = starArr.pop()
if (tmp[0] === '.') {
return true
} else {
let i = s.length - 1
while (i >= 0) {
if (s[i] === tmp[0]) {
i--
} else { // 没匹配到
return costStarArr(s.substring(0, i + 1), starArr)
}
}
return true
}
}
return false
}
Java 实现
public boolean isMatch(String s, String p) {
if (s == null || p == null)
return false;
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n+1];
dp[0][0] = true;
for (int i = 0; i < n; i++) {
//如果p的第i+1个字符也就是p.charAt(i)是"*"的话,
//那么他就可以把p的第i个字符给消掉(也就是匹配0次)。
//我们只需要判断p的第i-1个字符和s的前0个字符是否匹
//配即可。比如p是"a*b*",如果要判断p的第4个字符
//"*"和s的前0个字符是否匹配,因为字符"*"可以消去
//前面的任意字符,只需要判断p的"a*"和s的前0个字
//符是否匹配即可
if (p.charAt(i) == '*' && dp[0][i - 1]) {
dp[0][i + 1] = true;
}
}
……
}
// 作者:sdwwld
// 链接:https://leetcode-cn.com/problems/regular-expression-matching/solution/dong-tai-gui-hua-he-di-gui-liang-chong-fang-shi-2/
class Solution {
public:
bool isMatch(string s, string p) {
return match(s.data(), p.data());
}
bool match(char* s, char* p) {
if (!*p) return !*s;
if (*(p + 1) != '*')
return *s == *p || (*p == '.' && *s != '\0') ? match(s + 1, p + 1) : false;
else
return *s == *p || (*p == '.' && *s != '\0') ? match(s, p + 2) || match(s + 1, p) : match(s, p + 2);
//或者return (*s == *p || (*p == '.' && *s != '\0')) && match(s + 1, p) || match(s, p + 2);
}
};
// 作者:OrangeMan
// 链接:https://leetcode-cn.com/problems/regular-expression-matching/solution/cjian-ji-dai-ma-ti-jie-ming-tian-xie-by-orangeman/
Python 实现
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p: return not s # 结束条件
first_match = (len(s) > 0) and p[0] in {s[0], '.'}
# 先处理 `*`
if len(p) >=2 and p[1] == '*':
# 匹配0个 | 多个
return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
# 处理 `.` ,匹配一个
return first_match and self.isMatch(s[1:], p[1:])
#作者:dz-lee
#链接:https://leetcode-cn.com/problems/regular-expression-matching/solution/jian-ming-qing-xi-xie-fa-python3xiang-xi-zhu-shi-b/
其他
- 原题leetcode链接:https://leetcode-cn.com/problems/regular-expression-matching/
- 合作方:JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明:leetcode 题解 | 每日一题
更多相关文章
- 008. 字符串转换整数 (atoi) | Leetcode题解
- 003. 无重复字符的最长子串 | Leetcode题解
- W3C TPAC 大会上的 Service workers 内容总结[每日前端夜话0xCD]
- Jquery对选取到的元素显示指定的长度,对于的字符串用“...”显示
- 将字符串数组发布到.net-core mvc
- 尝试用动态内容填充分享Twitter链接
- js或Jquery中判断字符串中是否有换行符或回车符/n
- 在可观察的内容中订阅
- 使用javascript进行内容占位符问题的第二个css
随机推荐