【LeetCode】10. Regular Expression Matching(C++)

前端之家收集整理的这篇文章主要介绍了【LeetCode】10. Regular Expression Matching(C++)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

地址:https://leetcode.com/problems/regular-expression-matching/

题目:

Given an input string (s) and a pattern (p),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).

Note:

s could be empty and contains only lowercase letters a-z.

p could be empty and contains only lowercase letters a-z,and characters like . or *.


Example 1:

Input: s = “aa” p = “a”


Output: false


Explanation: “a” does not match the entire string “aa”.

Example 2:

Input: s = “aa” p = “a*”


Output: true


Explanation: ‘*’ means zero or more of the precedeng element,‘a’. Therefore,by repeating ‘a’ once,it becomes “aa”.

Example 3:

Input: s = “ab” p = “.*”


Output: true


Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:

Input: s = “aab” p = “cab”


Output: true


Explanation: c can be repeated 0 times,a can be repeated 1 time. Therefore it matches “aab”.

Example 5:

Input: s = “mississippi” p = “misisp*.”


Output: false

理解:

字符串的正则匹配,*可以匹配0个或多个字符,.可以匹配一个任意字符


思路是从头开始匹配,先看s[i]和p[j]是不是相同,或者p[j]=='.',如果是,当前位置是匹配的。


‘*’如果有,必然出现在j+1的位置。

如果p[j+1]=='*',需要判断两种情况。

s[i]开始的字符串和p[j+2]开始的字符串是否匹配,即*匹配了0个字符;

或者s[i]和p[j]是否相同,且s[i+1]和p[j]是否相同,即*匹配了一个字符。

否则,判断s[i]和p[j]是否相同,且s[i+1]和p[j+1]是否相同。

实现1:

最简单的递归实现,由于不停的复制string,效率很低

class Solution {

public:

bool isMatch(string s,string p) {

if (p.empty()) return s.empty();

bool first_match = (!s.empty() && (p.at(0) == s.at(0) || p.at(0) == '.'));

if (p.length() >= 2 && p.at(1) == '*') {

return isMatch(s,p.substr(2)) || (first_match && isMatch(s.substr(1),p));

}

else

return first_match&& isMatch(s.substr(1),p.substr(1));

}

};

实现2:

使用下标,代替了字符串复制

enum class Match {

FALSE,TRUE,UNKNOWN

};

class Solution {

vector> result;

public:

bool isMatch(string s,string p) {

result = vector>(s.length() + 1,vector(p.length() + 1,Match::UNKNOWN));

return dp(0,s,p);

}

bool dp(int i,int j,const string& s,const string& p) {

if (result[i][j] != Match::UNKNOWN)

return result[i][j] == Match::TRUE;

bool res;

if (j == p.length())

res = (i == s.length());

else {

bool first_match = i < s.length() && (s.at(i) == p.at(j) || p.at(j) == '.');

if (j + 1 < p.length()&&p.at(j+1)=='*') {

res = dp(i,j + 2,p) || (first_match&&dp(i + 1,j,p));

}

else {

res = first_match&&dp(i + 1,j + 1,p);

}

}

result[i][j] = res ? Match::TRUE : Match::FALSE;

return res;

}

};

实现3:

上面的实现2,还是使用递归的方式,然而前面的位置是与后面的位置有关的,因此可以从后向前,记录后面的判断结果,避免递归调用

class Solution {

vector> dp;

public:

bool isMatch(string s,string p) {

dp = vector>(s.length() + 1,vector(p.length() + 1,false));

dp[s.length()][p.length()] = true;

for (int i = s.length(); i >= 0; --i)

for (int j = p.length() - 1; j >= 0; --j) {

bool first_match = i < s.length() && (s.at(i) == p.at(j) || p.at(j) == '.');

if (j + 1 < p.length() && p.at(j + 1) == '*') {

dp[i][j] = dp[i][j + 2] || (first_match &&dp[i + 1][j]);

}

else {

dp[i][j] = (first_match && dp[i + 1][j + 1]);

}

}

return dp[0][0];

}

};

原文链接:https://www.f2er.com/express/61904.html

猜你在找的Express 相关文章