本文共 1499 字,大约阅读时间需要 4 分钟。
题目链接:https://leetcode.com/problems/interleaving-string/
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc"
,
s2 = "dbbca"
,
When s3 = "aadbbcbcac"
, return true.
When s3 = "aadbbbaccc"
, return false.
思路:二维动态规划的问题, dp[i][j]代表s1[0, i-1]子串和s2[0, j-1]子串是否和s3[0, i+j-1]子串相匹配
分两种情况讨论:
1. 如果s3[i+j-1] = s1[i-1], 则 dp[i][j] = dp[i-1][j],即如果s3[i+j-1] 与s1[i-1]相等,则dp[i][j]的状态由去掉相等位后的子状态dp[i-1][j]决定
2. 如果s3[i+j-1] = s2[j-1], 则 dp[i][j] = dp[i][j-1],即如果s3[i+j-1] 与s2[j-1]相等,则dp[i][j]的状态由去掉相等位后的子状态dp[i][j-1]决定
此两种状态只要一个为真,则dp[i][j]为真
需要注意的初始条件:
dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1])
dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1])
可以理解为另一个串为空的状态下,此串和s3必须每一位都相等才可以转化,所以如果上一为不相等,则下一位必然不相等
具体代码如下:
class Solution {public: bool isInterleave(string s1, string s2, string s3) { int len1 = s1.size(), len2 = s2.size(), len3 = s3.size(); if(len3 != len1+len2) return false; vector> dp(len1+1, vector (len2+1, false)); dp[0][0] = true; for(int i=1; i<=len1;i++) if(s1[i-1]==s3[i-1]&&dp[i-1][0]) dp[i][0]=true; for(int i=1; i<=len2;i++) if(s2[i-1]==s3[i-1]&&dp[0][i-1]) dp[0][i]=true; for(int i = 1; i <= len1; i++) { for(int j = 1; j <= len2; j++) { if(s3[i+j-1] == s1[i-1] && dp[i-1][j]) dp[i][j] = true; if(s3[i+j-1] == s2[j-1] && dp[i][j-1]) dp[i][j] = true; } } return dp[len1][len2]; }};
转载地址:http://uslbn.baihongyu.com/