原题链接:http://oj.leetcode.com/problems/regular-expression-matching/这个题目比较常见,但是难度还是比较大的。我们先来看看brute force怎么解决。基本思路就是先看字符串s和p的从i和j开始的子串是否匹配,用递归的方法直到串的最后,最后回溯回来得到结果。假设现在走到s的i位置,p的j位置,情况分为下列两种:(1)p[j+1]不是'*'。情况比较简单,只要判断当前s的i和p的j上的字符是否一样(如果有p在j上的字符是'.',也是相同),如果不同,返回false,否则,递归下一层i+1,j+1;(2)p[j+1]是'*'。那么此时看从s[i]开始的子串,假设s[i],s[i+1],...s[i+k]都等于p[j]那么意味着这些都有可能是合适的匹配,那么递归对于剩下的(i,j+2),(i+1,j+2),...,(i+k,j+2)都要尝试(j+2是因为跳过当前和下一个'*'字符)。实现代码如下:public boolean isMatch(String s, String p) {
return helper(s,p,0,0);
}
private boolean helper(String s, String p, int i, int j)
{
if(j==p.length())
return i==s.length();
if(j==p.length()-1 || p.charAt(j+1)!='*')
{
if(i==s.length()|| s.charAt(i)!=p.charAt(j) && p.charAt(j)!='.')
return false;
else
return helper(s,p,i+1,j+1);
}
//p.charAt(j+1)=='*'
while(i<s.length() && (p.charAt(j)=='.' || s.charAt(i)==p.charAt(j)))
{
if(helper(s,p,i,j+2))
return true;
i++;
}
return helper(s,p,i,j+2);
}
接下来我们考虑如何优化brute
force算法,熟悉动态规划的朋友可能发现了,其实这个思路已经很接近动态规划了。动态规划基本思想就是把我们计算过的历史信息记录下来,等到要用到的时候就直接使用,不用重新计算。在这个题里面,假设我们维护一个布尔数组res[i][j],代表s的前i个字符和p的前j个字符是否匹配(注意这里res的维度是s.length()+1,p.length()+1)。递推公式跟上面类似,分三种种情况:(1)p[j+1]不是'*'。情况比较简单,只要判断如果当前s的i和p的j上的字符一样(如果有p在j上的字符是'.',也是相同),并且res[i][j]==true,则res[i+1][j+1]也为true,res[i+1][j+1]=false;(2)p[j+1]是'*',但是p[j]!='.'。那么只要以下条件有一个满足即可对res[i+1][j+1]赋值为true: 1)res[i+1][j]为真('*'只取前面字符一次); 2)res[i+1][j-1]为真('*'前面字符一次都不取,也就是忽略这两个字符); 3)res[i][j+1] && s[i]==s[i-1] && s[i-1]==p[j-1](这种情况是相当于i从0到s.length()扫过来,如果p[j+1]对应的字符是‘*’那就意味着接下来的串就可以依次匹配下来,如果下面的字符一直重复,并且就是‘*’前面的那个字符)。(3)p[j+1]是'*',并且p[j]=='.'。因为".*"可以匹配任意字符串,所以在前面的res[i+1][j-1]或者res[i+1][j]中只要有i+1是true,那么剩下的res[i+1][j+1],res[i+2][j+1],...,res[s.length()][j+1]就都是true了。这道题有个很重要的点,就是实现的时候外层循环应该是p,然后待匹配串s内层循环扫过来。代码如下:public boolean isMatch(String s, String p) {
if(s.length()==0 && p.length()==0)
return true;
if(p.length()==0)
return false;
boolean[][] res = new boolean[s.length()+1][p.length()+1];
res[0][0] = true;
for(int j=0;j<p.length();j++)
{
if(p.charAt(j)=='*')
{
if(j>0 && res[0][j-1]) res[0][j+1]=true;
if(j<1) continue;
if(p.charAt(j-1)!='.')
{
for(int i=0;i<s.length();i++)
{
if(res[i+1][j] || j>0&&res[i+1][j-1]
|| i>0 && j>0 && res[i][j+1]&&s.charAt(i)==s.charAt(i-1)&&s.charAt(i-1)==p.charAt(j-1))
res[i+1][j+1] = true;
}
}
else
{
int i=0;
while(j>0 && i<s.length() && !res[i+1][j-1] && !res[i+1][j])
i++;
for(;i<s.length();i++)
{
res[i+1][j+1] = true;
}
}
}
else
{
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')
res[i+1][j+1] = res[i][j];
}
}
}
return res[s.length()][p.length()];
}
对比以上两种做法,其实思路基本类似,动态规划优势在于对于前面计算过得信息不需要再重复计算,而brute
force则每次重新计算。上面两种算法中,动态规划的时间复杂度是O(n^2),空间复杂度也是O(n^2)。而brute force的递归算法最坏情况是指数量级的复杂度。这种题目在面试中算是比较难的题目,因为分情况比较多,如果不熟悉比较难在面试中理清思路并且做对,我不是很喜欢,但是在面经中却经常看到,所以还是得搞熟悉比较好。类似的题目有Wildcard
Matching,那个还更简单一些,不过思路是基本一致的,只是少分一点情况。
分享到:
相关推荐
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。...Expression Matching 25.3% 困难 11 Container With Most Water 59.3% 中等 12 Integer to Roman 61.8% 中等 13 Roman to In
lru cache leetcode Leetcode ...Expression Matching 动态规划,列出转换方程即可,注意初值 记T[i][j] = 是否S[0:i]和P[0:j]匹配 再分类讨论,其中pattern *分为0, 1, more三种类型 0: i不变, j+1
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
Expression Matching 递归匹配 wildcard matching 动态规划 longest common prefix , 简单 valid number, hard, 用有限自动机 integer to roman ,easy , 模拟 roman to integer ,easy , 模拟 count and say , easy ,...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
[10_regular-expression-matching.cpp] [100_same-tree.cpp] [1001_sorted-merge-lcci.cpp] [101_对称树.cpp] [102_binary-tree-level-order-traversal.cpp] [103_binary-tree-zigzag-level-order-traversal.cpp] ...
leetcode 答案 leet code 这是我的leetcode答案,语言主要是用python。很多算法不是最优,甚至很槽糕,有空就会优化 目前完成了: Two Sum Add Two Numbers Longest ...Regular Expression Matching
(/problems/regular-expression-matching/) 24.1% 难253 38.9% 中15 21.6% 中277 寻找名人 (/problems/find-the-celebrity/) 35.4% 中等158 读取 N 个字符给定 Read4 II - 多次调用 (/problems/read-n-...
35%2☆ ☆27%3☆ ☆24%4☆ ☆ ☆21%5☆ ☆25%6☆ ☆26%7☆24%8☆ ☆13%9Palindrome Number☆35%10Regular Expression Matching☆ ☆ ☆24%:red_heart:11Container With Most Water☆ ☆36%12Integer to R
lru cache leetcode leetcode leetcode solutions in C++ 微信公众号:曲奇泡芙 (互联网&车联网技术) ..../0010-regular-expression-matching.cpp ./0011-container-with-most-water.cpp ./0012-int
leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...
leetcode数组下标大于间距 5. Longest Palindromic Substring 这里使用menecher方法,就是动态规划,首先在原先的字符串之间插入'#, 这样可以统一处理奇数串和偶数串, 使用两个变量纪录状态, far_pos表示最长回文...
https://leetcode.com/problems/regular-expression-matching/ Regular Expression Matching 100 https://leetcode.com/problems/same-tree/ Same Tree 101 https://leetcode.com/problems/symmetric-tree/ ...
LeetCode判断字符串是否循环 ...Expression Matching Difficult 13 Roman to Integer Easy 15 Medium 21 Easy 26 Remove Duplicates from Sorted Array Easy 142 Medium 191 Number of 1 Bit
0010_Regular_Expression_Matching 0011_Container_With_Most_Water 0012_Integer_to_Roman 0013_Roman_to_Integer 0014_Longest_Common_Prefix 0015_3总和 0016_3Sum_Closest 0017_Letter_Combinations_of_a_Phone_...
Expression Matching 011 Container With Most Water 012 Integer to Roman 013 Roman to Integer 014 Longest Common Prefix 015 3Sum 016 3Sum Closest 017 Letter Combinations of a Phone Number 018 4Sum 020 ...
leetcode正则表达式 DP-7 Problem1 Edit Distance () Problem2 Regular Expression Matching ()
leetcode 跳跃 LeetCode Solved by ...Expression Matching 正则表达式匹配 11. Container With Most Water 盛最多水的容器 12. Integer to Roman 整数转罗马数字 13. Roman to Integer 罗马数字转
LeetCode 自己刷LeetCode整理的一些题解笔记,有什么错误欢迎指出。 带:club_suit:为力扣2020.3.1开始的每日一题打卡 ...Regular-Expression-Matching C++, Python Hard 11:club_suit: Container-With-
10.Regular Expression Matching: 递归的方法:当前正则第二个字符不为'*',很简单,比较当前,两个指针都往右移动即可,继续这样比较。如果为空,则有两种方式,第一种是正则的指针往后移动,字符串的保持不变,另一...