Regular Expression Matching问题及解法

本文主要是介绍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

思路：这可以作为一种典型的动态规划问题。我么可以定义状态P[i][j]。当s[0...i)匹配p[0...j)时。P[i][j] = true；否则为false。

状态转换的等式如下

1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

以下是实现的代码

class Solution {
public:bool isMatch(string s, string p) {int m = s.length(), n = p.length(); vector<vector<bool> > dp(m + 1, vector<bool> (n + 1, false));dp[0][0] = true;for (int i = 0; i <= m; i++)for (int j = 1; j <= n; j++)if (p[j - 1] == '*')dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');return dp[m][n];}
};

代码不难理解，有疑问的欢迎交流~~

这篇关于Regular Expression Matching问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---