当前位置: 首页> 科技> 名企 > 子域名大全查询_手机网站设计欣赏_网址大全名称_深圳关键词推广整站优化

子域名大全查询_手机网站设计欣赏_网址大全名称_深圳关键词推广整站优化

时间:2025/7/10 10:06:08来源:https://blog.csdn.net/s478527548/article/details/146092214 浏览次数:2次
子域名大全查询_手机网站设计欣赏_网址大全名称_深圳关键词推广整站优化

很明显的动态规划,就是怎么用想了一段时间。(开始还怀疑过是不是双指针,发现不行,因为会出现s3的下一个字符同时能够匹配到两个字符串字符的情况)

然后就是构建数组dp[101][101],数组代表前x个s1字符和前y个s2字符是否与前x+y个s3是交错字符串。

不断递归就行了:

class Solution {
public:string s1,s2,s3;int dp[101][101];bool dg(int x,int y){if(s1.size()==x&&s2.size()==y){dp[x][y]=1;return 1;}if(dp[x][y]!=-1) return dp[x][y]==1;bool b=0;if(s1.size()>x&&s1[x]==s3[x+y]){b=b|dg(x+1,y);}if(s2.size()>y&&s2[y]==s3[x+y]){b=b|dg(x,y+1);}dp[x][y]=b;return b;}bool isInterleave(string s1, string s2, string s3) {if(s1.size()+s2.size()!=s3.size()) return 0;this->s1=s1;this->s2=s2;this->s3=s3;memset(dp,-1,sizeof(dp));dg(0,0);return dp[s1.size()][s2.size()]==1;}
};

学到了一点东西就是可以用-1、0、1三种状态分别代表未判断、不是交错字符串、是交错字符串,之前也用到过这种做法,可以降低复杂度。

关键字:子域名大全查询_手机网站设计欣赏_网址大全名称_深圳关键词推广整站优化

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: