动态规划学习——通符串匹配，正则表达式
目录
一，通符串匹配
1.题目
给你一个输入字符串 (
s) 和一个字符模式 (p) ，请你实现一个支持?'?'?和?'*'?匹配规则的通配符匹配：
'?'?可以匹配任何单个字符。'*'?可以匹配任意字符序列（包括空字符序列）。判定匹配成功的充要条件是：字符模式必须能够?完全匹配?输入字符串（而不是部分匹配）。
?示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。示例 2：
输入：s = "aa", p = "*" 输出：true 解释：'*' 可以匹配任意字符串。示例 3：
输入：s = "cb", p = "?a" 输出：false 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。提示：
0 <= s.length, p.length <= 2000s?仅由小写英文字母组成p?仅由小写英文字母、'?'?或?'*'?组成
2.题目接口
class Solution {
public:
bool isMatch(string s, string p) {
}
};3，解题思路及其代码
在做动态规划问题时一般都是按照以下几步来走的：
1.确定状态转移方程
?像这种两个字符串的问题，一般都是定义二维的dp表按照两个字符串的第i和j下标位置来解决问题的。所以在这里定义dp[i][j]表示p在区间[1,j]中的字符是否存在能够匹配s在[1，i]中的字符。
2.状态转移方程
以s的第i个位置，p的第j个位置为研究对象来研究问题。此时分三种情况：1.s[i] == p[j]，或者p[j] == '?',在这种情况下dp[i][j] = dp[i-1][j-1]。
2.p[j] == "*"，在这种情况下就要看这个*可以顶替掉多少个s中的字符了：
顶替0个：dp[i][j] = dp[i][j-1]
顶替1个：dp[i][j] = dp[i-1][j-1]
顶替2个：dp[i][j] = dp[i-2][j-1]
顶替3个：dp[i][j] = dp[i-3][j-1]......
在以上i种情况下，我们只要找到一个为真便可以了。所以dp[i][j] = dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1].....。但是这样表示的话就需要遍历一遍，所以我们必须要优化以上状态表达，优化成为dp[i][j] = dp[i][j-1]||dp[i-1][j]。通过数学推导得知（将dp[i][j-1]后面的表达式转为一个状态表示）。
3.s[i]!=p[j]并且不是以上情况，在这种条件下dp[i][j]直接就是false。
3.初始化：
1.在字符串问题里，我们一般会在字符串的开头加上一个' '。
?2.因为*是可以匹配空的，所以当s字符串为空串时p为空串或者p全为*时也是可以匹配的。
初始化如下：
s = ' '+s; p = ' '+p; dp[0][0] = true; //初始化：当我的s是一个空串时，我的p都是* for(int i = 1;i<n+1;i++) if(dp[0][i-1]&&p[i] == '*') dp[0][i] = true;4.填表顺序
根据状态转移方程很容易得出dp表的填写顺序是从左到右，从上到下。
5.返回值
?根据状态表示可知返回值是dp[m][n](m表示s的长度，n表示p的长度)? ??
代码：
class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); vector<vector<bool>>dp(m+1,vector<bool>(n+1));//dp[i][j]表示s,p分别以i,j结尾能不能完全匹配 s = ' '+s; p = ' '+p; dp[0][0] = true; //初始化：当我的s是一个空串时，我的p都是* for(int i = 1;i<n+1;i++) if(dp[0][i-1]&&p[i] == '*') dp[0][i] = true; //以i,j为结尾研究问题 for(int i = 1;i<m+1;i++) { for(int j = 1;j<n+1;j++) { //分两种情况 if(p[j] == s[i]||p[j] == '?') { dp[i][j] = dp[i-1][j-1]; } else if(p[j] == '*') { //这颗*可以若干个字符，那可以配0个或者无数个得到的状态转移方程如下 //如果不匹配dp[i][j] = dp[i][j-1] //如果匹配1个dp[i][j] = dp[i-1][j-1] //如果匹配两个dp[i][j] = dp[i-2][j-1] //....... //在上面的情况中我们只要找到一种便可以 //dp[i][j] = dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]...... //优化：将上面的i个表达式变成n个表达式表示：dp[i][j] = dp[i][j-1]||dp[i-1][j] dp[i][j] = dp[i-1][j]||dp[i][j-1]; } } } return dp[m][n]; } };
二，正则表达
?1.题目
给你一个字符串?
s?和一个字符规律?p，请你来实现一个支持?'.'?和?'*'?的正则表达式匹配。
'.'?匹配任意单个字符'*'?匹配零个或多个前面的那一个元素所谓匹配，是要涵盖?整个?字符串?
?s的，而不是部分字符串。示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。示例 2:
输入：s = "aa", p = "a*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例?3：
输入：s = "ab", p = ".*" 输出：true 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。提示：
1 <= s.length?<= 201 <= p.length?<= 20s?只包含从?a-z?的小写字母。p?只包含从?a-z?的小写字母，以及字符?.?和?*。- 保证每次出现字符?
*?时，前面都匹配到有效的字符
2.题目接口
class Solution {
public:
bool isMatch(string s, string p) {
}
};3.解题思路及其代码
但是这道题跟第一道题何其相似啊！！！'.'和'?'匹配规则是一样的，但是注意两个题目的'*'的匹配规则是是不一样的。所以在'*"和初始化处就要稍加改造了，改造如下：
初始化：
for(int i = 2;i<n+1;i+=2) if(dp[0][i-2]&&p[i] == '*') dp[0][i] = true;当遇到"*"时填表情况如下：
else if(p[j] == '*') { //按照题意在*前面一定有字符 if(p[j-1] == '.')//无敌匹配 { dp[i][j] = dp[i][j-2]||dp[i-1][j]; } else//不是. { //判断后再匹配 if(p[j-1] == s[i]) { dp[i][j] = dp[i][j-2]||dp[i-1][j]; } else { dp[i][j] = dp[i][j-2]; } }解题代码如下：
class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); //经典加上空格 s = ' '+s; p = ' '+p; //经典二维dp表 vector<vector<bool>>dp(m+1,vector<bool>(n+1)); dp[0][0] = true; //初始化:当s为空串时 for(int i = 2;i<n+1;i+=2) if(dp[0][i-2]&&p[i] == '*') dp[0][i] = true; for(int i = 1;i<m+1;i++) { for(int j = 1;j<n+1;j++) { //分情况讨论 if(p[j] == '.'||s[i] == p[j]) { //i,j位置匹配上了就得看dp[i-1][j-1] dp[i][j] = dp[i-1][j-1]; } else if(p[j] == '*') { //按照题意在*前面一定有字符 if(p[j-1] == '.')//无敌匹配 { dp[i][j] = dp[i][j-2]||dp[i-1][j]; } else//不是. { //判断后再匹配 if(p[j-1] == s[i]) { dp[i][j] = dp[i][j-2]||dp[i-1][j]; } else { dp[i][j] = dp[i][j-2]; } } } } } return dp[m][n]; } };
三，交错字符串
?1.题目
给定三个字符串?
s1、s2、s3，请你帮忙验证?s3?是否是由?s1?和?s2?交错?组成的。两个字符串?
s?和?t?交错?的定义与过程如下，其中每个字符串都会被分割成若干?非空?子字符串：
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- 交错?是?
s1 + t1 + s2 + t2 + s3 + t3 + ...?或者?t1 + s1 + t2 + s2 + t3 + s3 + ...注意：
a + b?意味着字符串?a?和?b?连接。示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出：true示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出：false示例 3：
输入：s1 = "", s2 = "", s3 = "" 输出：true提示：
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1、s2、和?s3?都由小写英文字母组成进阶：您能否仅使用?
O(s2.length)?额外的内存空间来解决它?
2，题目接口
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
}
};3.解题思路及其代码
在看到三个字符串时，我就已经犯蒙了。感觉二维的dp表好像已经解决不了问题了，但是其实是可以解决问题的。解决步骤如下：
1，状态表示
仍然是开一个二维dp表dp[][]。仍然以s1的第i个位置和s2的第j个位置为研究对象研究问题。dp[i][j]表示s1的【1，i]区间和s2的【1，j】区间的字符能不能组成s3的【1，i+j】区间的字符。
2.状态转移方程
在这里我们也是分两种情况来讨论：
1，当s1[i] == s3[i+j]时，dp[i][j] = dp[i-1][j]。
2， 当s2[j] == s3[i+j]时，dp[i][j] = dp[i][j-1]。
3, 当以上两种情况都不成立的话，dp[i][j] = false。
所以dp[i][j] = (s1[i]==s3[i+j]&&dp[i-][j])&&(s2[j] == s3[i+j]&&dp[i][j-1])。
3，初始化
为了让下标对应所以得在每个字符的前面加上" "。
//加上空格，因为空格有意义 s1 = " "+s1; s2 = " "+s2; s3 = " "+s3;当s1和s2都是空串时，能够组成空串
//初始化 dp[0][0] = true;当有一个串为空时，另一个串要和s3一一匹配
for(int i =1;i<m+1;i++)//代表s2为空串 { if(s1[i] == s3[i]) { dp[i][0] = true; } else { break; } } for(int i =1;i<n+1;i++)//代表s1为空串 { if(s2[i] == s3[i]) { dp[0][i] = true; } else { break; } }4，填表顺序
按照状态转移方程可知填表顺序为：从上到下，从左到右。
5，返回值
返回dp[m][n]
代码如下：
class Solution { public: bool isInterleave(string s1, string s2, string s3) { int m = s1.size(); int n = s2.size(); if(m+n!=s3.size()) return false; //二维数组表示以i,j位置为结尾能够组成s3的i+j vector<vector<bool>>dp(m+1,vector<bool>(n+1)); //加上空格，因为空格有意义 s1 = " "+s1; s2 = " "+s2; s3 = " "+s3; //初始化 dp[0][0] = true; for(int i =1;i<m+1;i++)//代表s2为空串 { if(s1[i] == s3[i]) { dp[i][0] = true; } else { break; } } for(int i =1;i<n+1;i++)//代表s1为空串 { if(s2[i] == s3[i]) { dp[0][i] = true; } else { break; } } //经典以i,j位置为研究对象 for(int i = 1;i<m+1;i++) { for(int j = 1;j<n+1;j++) { dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]) || (s2[j] == s3[i + j] && dp[i][j - 1]); } } return dp[m][n]; } };
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！