1 Interleaving String
Total Accepted: 11803 Total
Submissions: 62216My Submissions
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.
注意右下递推中边界条件：i=0? j=0?
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n=s1.length(),m=s2.length();
if(n+m!=s3.length()) return false;///@@@error: s3.length can be not qual to s1's + s2's
vector<vector<bool> > s(2,vector<bool>(m+1,false));//
s[0][0]=true;
for(int i=0;i<=n;i++){// s3[i+j-1]
for(int j=0;j<=m;j++){
if(i==0&&j==0) continue;
s[i%2][j]=(i>0 && s[(i+1)%2][j] && s1[i-1]==s3[i+j-1] ) || (j>0 && s[i%2][j-1] && s2[j-1]==s3[i+j-1]);//右下递推
} //@@@error: s[(i-1)%2] ,when i-1=-1,-1%2==-1,this cause array index overflow
}
return s[n%2][m];
}
};
2 Distinct Subsequences
Total Accepted: 12288 Total
Submissions: 49861My Submissions
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is
a subsequence of "ABCDE" while "AEC" is
not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
class Solution {
public:
int numDistinct(string S, string T) {
int n=S.length(),m=T.length();
if(n==0||m==0) return 0;
vector<vector<int> > cnt(2,vector<int>(n,0));
for(int i=0;i<m;i++){
cnt[i%2]=vector<int>(n,0);
for(int j=0;j<n;j++){
cnt[i%2][j]=j>0?cnt[i%2][j-1]:0;//@error: j>=1, not j>1
if(T[i]==S[j]){///@@error: T[i]==S[j] fault as S[i]==T[j]. remember here T is the pattern, S is the matched str
int t=(i>0&&j>0)?cnt[(i+1)%2][j-1]:i==0?1:0;//@error: i==0 fault as i==0&&j==0. i==0 so the previous T[0~i-1] matches S[0~j-1]
cnt[i%2][j]+=t;//@@@error:+=cnt[(i+1)%2][j-1];
}
}
}
return cnt[(m-1)%2][n-1];
}
};
3 Min Edit Distance
f[i][j] = min( f[i-1][j]+1, f[i][j-1] +1, f[i-1][j-1] if(a[i-1]==b[j-1]) )
4 LCS(longest common sequence)
f[i][j] = max( f[i-1][j], f[i][j-1], f[i-1][j-1] +1 if(a[i-1]==b[j-1] )
5 字符串交错
问题
解答
f[i][j] = f[i-1][j] && A[i-1] == C[i+j-1] || f[i][j-1] && B[j-1] == C[i+j-1]
初始化：f[0][i] = B.prefix(i) == C.prefix(i); f[i][0] = A.prefix(i) == C.prefix(i);
时间和空间复杂度均为O(n^2)