1、最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
【Link】

思路：很经典的dp题目了

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n1=text1.length();int n2=text2.length();vector >dp(n1+1,vector(n2+1,0));for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}return dp[n1][n2];}
};

2、字符串交织

给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。
两个字符串 s 和 t 交织 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交织 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
提示：a + b 意味着字符串 a 和 b 连接。
【Link】

WA思路：一开始想到的是根据上一题的灵感，对于s3而言，只需要s1和s2同时和s3的最长公共子序列为s1和s2本身即可，通过了90%案例，但是忽视了s1和s2对于同一个字符“争夺”的问题,比如：

"aabd"
"abdc"
"aabdbadc"

WA code

class Solution {
public:int longestCommonSubsequence(string& text1, string& text2) {int n1=text1.length();int n2=text2.length();vector >dp(n1+1,vector(n2+1,0));for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}return dp[n1][n2];}bool isInterleave(string s1, string s2, string s3) {if(s3.length()!=s1.length()+s2.length()){return false;}vectorabc(26,0);for(int i=0;iabc[s3[i]-'a']++;}for(int i=0;iabc[s1[i]-'a']--;if(abc[s1[i]-'a']<0){return false;}}for(int i=0;iabc[s2[i]-'a']--;if(abc[s2[i]-'a']<0){return false;}}//首先两个必须都要满足最长公共子串if(longestCommonSubsequence(s1, s3)==s1.length()){if(longestCommonSubsequence(s2, s3)==s2.length()){return true;}}return false;}
};

DP思路：比较难以想到的是如何定义dp数组，其实可以定义dp[i][j]为前i个s1和前j个s2可否交织成s3的前p=i+j个元素，得到如下的DP公式：

dp[i][j]表示的是可否满足s1的前i个元素和s2的前j个元素可以交织成s3的前p=i+j个元素
dp[0][0]肯定为true
dp[i][j]=dp[i-1][j]&&s1[i-1]==s3[p]
dp[i][j]=dp[i][j-1]&&s2[j-1]==s3[p]

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n1=s1.length();int n2=s2.length();int n3=s3.length();if(n3!=n1+n2){return false;}vector >dp(n1+1,vector(n2+1,false));dp[0][0]=true;int p;for(int i=0;i<=n1;i++){for(int j=0;j<=n2;j++){p=i+j-1;if(i>0){dp[i][j] = dp[i][j]| (dp[i-1][j]&&s3[p]==s1[i-1]);}if(j>0){dp[i][j] = dp[i][j]| (dp[i][j-1]&&s3[p]==s2[j-1]);}}}return dp[n1][n2];}
};