题目描述
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int numDistinct(string s, string t) {
int ls = s.length();
int lt = t.length();
long **dp = new long*[lt + 1];
for (int i = 0; i <= lt; i++)
dp[i] = new long[ls + 1];
for (int i = 0; i <= ls; i++)
dp[0][i] = 1;
for (int i = 1; i <= lt; i++)
dp[i][0] = 0;
for (int i = 1; i <= lt; i++)
for (int j = 1; j <= ls; j++)
dp[i][j] = dp[i][j - 1] + (s[j - 1] == t[i - 1] ? dp[i - 1][j - 1] : 0);
return int(dp[lt][ls]);
}
|
注意可能会出现超过INT_MAX大小的中间结果。
难道要算出所有的子序列，然后在里面计数求和吗？
是不是傻，字符串，动态规划问题啊。
理解有误。没用的子函数放在下面的吧。晚安。
求全部子序列：
1
2
3
4
5
6
7
8
| void getsubstring(string s, string base, set<string>& vec, int index)
{
if (index == s.length())return;
vec.insert(base);
getsubstring(s, base, vec, index + 1);
vec.insert(base + s[index]);
getsubstring(s, base + s[index], vec, index + 1);
}
|
计数淄川出现的次数：
1
2
3
4
5
6
7
8
9
10
11
12
| std::string str("abcabdabcdsdabcds");
auto occurrences = [&str](const std::string &dest) {
size_t pos, pre = 0, count = 0;
while ( (pos = str.find(dest, pre)) != std::string::npos ) {
++count;
pre = pos + 1;
}
return count;
};
std::cout << occurrences("abc") << std::endl;
|
是真的菜。