编写c++代码给定字符串s和t,判断s是否为t的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
时间: 2024-05-15 13:14:14 浏览: 13
可以使用双指针法来解决这个问题,具体步骤如下:
1. 定义两个指针i和j,分别指向s和t的起始位置。
2. 依次比较s和t的每个字符,如果相同则i和j都向后移动一位,否则只移动j。
3. 如果i到达s的末尾,说明s是t的子序列,返回true;如果j到达t的末尾,说明s不是t的子序列,返回false。
以下是完整的C++代码实现:
```c++
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.size() && j < t.size()) {
if (s[i] == t[j]) {
i++;
}
j++;
}
return i == s.size();
}
```
相关问题
编写c++代码:给定字符串s和t,判断s是否为t的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
以下是使用双指针法(双下标)的C++代码实现:
```cpp
#include <iostream>
using namespace std;
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.size() && j < t.size()) {
if (s[i] == t[j]) {
i++;
}
j++;
}
return i == s.size();
}
int main() {
string s = "ace";
string t = "abcde";
if (isSubsequence(s, t)) {
cout << s << " is a subsequence of " << t << endl;
} else {
cout << s << " is not a subsequence of " << t << endl;
}
return 0;
}
```
输出结果为:
```
ace is a subsequence of abcde
```
给定字符串 s, 其特征子序列 t 满足: 子序列中的字符各不相同; s 中的各种字符都能在 t 中找到; 对于一个字符串 s,可能会对应多个特征子序列,其中字典序最小的特征序列称为“最优特征子序列”。 请写一个程序,返回字符串的最优特征子序列。要求时间复杂度不超过 O(N)。要求输入一行长度为N。然后输入一行长度为N的s字符串。输出要求的最优特征子序列。用C++代码实现
以下是C++代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 26;
char s[MAXN + 5]; // 输入的字符串
int cnt[MAXN + 5]; // 统计每个字符出现的次数
bool vis[MAXN + 5]; // 记录每个字符是否在特征子序列中出现过
int main() {
cin >> s;
int n = strlen(s);
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++; // 统计每个字符出现的次数
}
for (int i = 0; i < n; i++) {
if (!vis[s[i] - 'a']) { // 如果当前字符还没有出现在特征子序列中
while (!vis[s[i] - 'a'] && // 如果当前字符还没有出现在特征子序列中
cnt[s[i] - 'a'] > 0 && // 当前字符在剩余未处理的字符中仍然存在
(s[i] < s[n - 1] || cnt[s[i] - 'a'] > 1)) { // 当前字符比剩余未处理的字符中的最后一个字符小,或者当前字符在剩余未处理的字符中出现了多次
vis[s[i] - 'a'] = true; // 标记当前字符出现在特征子序列中
cnt[s[i] - 'a']--; // 将当前字符从剩余未处理的字符中删除
cout << s[i];
}
}
}
cout << endl;
return 0;
}
```
算法思路:
1. 统计每个字符出现的次数。
2. 对于输入的字符串 s,按照顺序依次处理每个字符。
3. 对于每个字符,如果它还没有出现在特征子序列中,就尝试将它加入到特征子序列中。
4. 如果当前字符在剩余未处理的字符中仍然存在,并且当前字符比剩余未处理的字符中的最后一个字符小,或者当前字符在剩余未处理的字符中出现了多次,那么就将当前字符加入到特征子序列中。
5. 不断重复步骤 4,直到不能再加入新的字符为止。
6. 输出特征子序列即为最优特征子序列。
时间复杂度为 O(N)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)