leetcode Regular Expression Matching || leetcode Wildcard Matching

10. 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
isMatch(“ab”, “.*”) → true
isMatch(“aab”, “c*a*b”) → true

题目地址:leetcode Regular Expression Matching

题意:’.’表示可以代替任何字符,’*’表示可以代替前面一个出现的字符,且可以代表任意个,给定字符串s和p,问s和p是否匹配。

aab和c*a*b为true时因为,p中第一个*代替0个c,第二个*代替两个a,于是可以变为aab,和s相同,所以为true

 

If the next character of p is NOT ‘*’, then it must match the current character of s. Continue pattern matching with the next character of both s and p.
If the next character of p is ‘*’, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p… Until we could not match any more characters.

 

C++

 Python版本正着写一直很慢。。

 

44. Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

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”, “*”) → true
isMatch(“aa”, “a*”) → true
isMatch(“ab”, “?*”) → true
isMatch(“aab”, “c*a*b”) → false

题目地址:leetcode Wildcard Matching

题目大意:和上面一题类似,?表示匹配任何字符,*表示匹配任意字符串序列,给定s和p,问是否匹配。

和上面一题的最大区别在于,*不在表示前面一个字符,而是可以变成任意字符串序列。

学着上面一题的思路,写了个递归,TLE ! 想到连续的几个*和一个是一样的!于是改了,依然TLE!

然后用dp了。

dp[i][j]为前i个s和前j p是否匹配。

则有:

  1. p[j]==’*’  dpi][j]=dp[i-1][j] || dp[i][j-1]  (*要么匹配当前的,要么不匹配)
  2. p[j] ≠’*’   dp[i][j]=dp[i-1][j-1]  (当然,p[j-1]==s[j-1] || p[j-1]==’?’ )

记得用两个一维数组即可,o(n*m)空间会超内存T^T。

嗯,还有就是要做一个剪枝,p长度为m,s长度为n,设p中’*’个数为cnt,如果n-cnt > m,显然无解。

C++

Python

 

 

 

C++ 递归TLE版:

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Regular Expression Matching || leetcode Wildcard Matching
本文地址:https://www.hrwhisper.me/leetcode-regular-expression-matching-leetcode-wildcard-matching/

听说长得好看的已经打赏了

codes, Leetcode . permalink.

One thought on “leetcode Regular Expression Matching || leetcode Wildcard Matching

  1. 第一个python 代码 有个数组越界的情况 就是p=‘*’ 的时候,取不到p[:-2],leetcode 测试代码有漏洞 要加一段代码
    if len(p)==1:
    if len(s)!=1:
    return False
    if p[0]!=’.’ and p[0]!=s[0]:
    return False
    return True

Leave a Reply

Your email address will not be published. Required fields are marked *