1.题目描述
给定一个字符串 (
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 = “cab”
输出: true
解释: ‘c’ 可以不被重复, ‘a’ 可以被重复一次。因此可以匹配字符串 “aab”。示例 5:
输入:
s = “mississippi”
p = “misisp*.”
输出: false
2.解题思路
方法1:
跟剑指offer的52题一致
这道题的核心其实在于分析’‘,对于’.’来说,它和任意字符都匹配,可把其当做普通字符。对于’‘的分析,我们要进行分情况讨论,当所有的情况都搞清楚了以后,就可以写代码了。
情况1:Patttern第二个字符是’*’时:
1.第一个字符不匹配(’.’与任意字符视作匹配),那么’*’只能代表匹配0次
‘ba’与’a*ba’,字符串不变,模式向后移动两个字符,然后匹配剩余字符串和模式
2.第一个字符匹配,那么’*’可能代表匹配0次,1次,多次,
(1)’aaa’与’a*aaa’: 匹配0次时,字符串不变,模式向后移动两个字符,然后匹配剩余字符串和模式;
(2)’aba’与’a*ba’:匹配1次时,字符串往后移动一个字符,模式向后移动2个字符;
(3)’aaaba’与’a*ba’:匹配多次时,字符串往后移动一个字符,模式不变;
情况2:Patttern第二个字符不是’*’时:
(1)如果字符串的第一个字符和模式中的第一个字符匹配,那么在字符串和模式上都向后移动一个字符,然后匹配剩余字符串和模式。
(2)如果字符串的第一个字符和模式中的第一个字符不匹配,那么直接返回false。
方法2:动态规划
定义一个dp[][]数组,其中d[i][j]表示s[0,i]和p[0][j]是否匹配
dp初始化:dp[0][0] = true,代表str为空串,pattern为空串的情况
求dp[0][j]即求str为空串,pattern是否匹配 当遇到后一个为 * 时,且dp[0][i-1]为true则匹配(匹配前面字符0次),标记dp[0][i+1] = true
情况1:当前字母匹配,str和pattern都往后移动一位
dp[i+1][j+1] = dp[i][j]
情况2:后一个pattern是 * ,前一个pattern跟str不匹配,str不变,pattern后移动两位
dp[i+1][j+1] = dp[i+1][j-1]
情况3:后一个pattern是 * ,前一个pattern跟str匹配
(1)匹配0次,str不动,pattern后移2位 dp[i+1][j+1] = dp[i+1][j-1] (2)匹配一次,str移动1位,pattern移动2位 dp[i+1][j+1] =dp[i][j-1] (3)匹配多次,str移动1次,pattern不动 dp[i+1][j+1] = dp[i][j+1]
3.代码
方法1:
1 | public static boolean isMatch(String str, String pattern) { |
方法2:动态规划
1 | public static boolean isMatch(String s, String p) { |