住房建设城乡网站,移动手机号码网站,学校网站群建设,wordpress哪个php版本好思路#xff1a;LCS
其实也是同一个类型的题目#xff0c;一般涉及到这种子序列的字符串问题的时候#xff0c;状态的设置基本上都应该是以...结尾为状态的。这里同样#xff0c;设置用dp[i][j]为s1,s2字符以i#xff0c;j结尾能否拼接成s3[ij]。
那么#xff0c;首先就…思路LCS
其实也是同一个类型的题目一般涉及到这种子序列的字符串问题的时候状态的设置基本上都应该是以...结尾为状态的。这里同样设置用dp[i][j]为s1,s2字符以ij结尾能否拼接成s3[ij]。
那么首先就是探讨一下转移方程怎么写。我们知道说是交错也就是交替拼接字符串。
我们需要考虑两种可能一种就是当前s1[i]字符与s3[ij-1]字符是否匹配如果说这个是匹配的这样还不够我们还需要看后面的子字符串是怎么样的情况所以除去这一个位置的字符我们去看dp[i-1][j]这个状态是不是能够达成。
同理当s2[j]s3[ij-1]的时候我们还需要看到dp[i][j-1]的状态是怎么样的。
以上的实现只需要用两个if语句实现就可以轮次判断即可。
注意这里还需要dp初始化想一下我们在s1为空或者s2为空的时候到底是个什么情况呢这个时候除了我们需要知道当前位置的字符匹配与否还需要知道dp[i-1][0]或者dp[0][i-1]这个时候的情况是不是能够达成条件所以初始化的时候需要额外注意。
dp[0][0]true这个是理所当然的。
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int ns3.size();if(n!s1.size()s2.size())return false;vectorvectorintdp(s1.size()10,vectorint(s2.size()10,0));dp[0][0]1;for(int i1;is1.size()dp[i-1][0];i){dp[i][0](s1[i-1]s3[i-1]);}for(int i1;is2.size()dp[0][i-1];i){dp[0][i](s2[i-1]s3[i-1]);}for(int i1;is1.size();i){for(int j1;js2.size();j){if(s1[i-1]s3[ij-1])dp[i][j]dp[i][j]|dp[i-1][j];if(s2[j-1]s3[ji-1])dp[i][j]dp[i][j]|dp[i][j-1];}}return dp[s1.size()][s2.size()];}
};
