最近,fried-chicken完全学明白了DFS搜索!于是学弟向他请教DFS搜索,fried-chicken热心的进行了讲解:

所谓DFS搜索,就是给定一个字符串 s,问能否找到 s 的一个子序列,使得该子序列的值为 "DFS" 或 "dfs"。

请你分别判断字符串 s 中是否含有 "DFS" 子序列与 "dfs" 子序列。

子序列的定义:从原字符串中选择一些字符,将这些字符按照其在原串中的顺序拼接起来,得到的就是原字符串的一个子序列。例如:"ABCDA"的子序列可以为"ACA"、"ABCDA"、"BA"等等,但不能为"ABE"、"CBA"、"AAD"。

输入格式

输入的第一行包括一个正整数 T (1 ≤ T ≤ 100),表示测试用例的组数。

对每组测试用例,第一行是一个正整数 n (1 ≤ n ≤ 50),表示输入字符串的长度。第二行是一个长度为 n 的字符串 s,保证字符串中只含有英语小写字母与英语大写字母。

输出格式

对于每组测试用例,输出空格分隔的两个数字,第一个数字表示是否含有 "DFS" 子序列,第二个数字表示是否含有 "dfs" 子序列。输出 "1" 表示含有,输出 "0" 表示不含有。

输入样例:

5
6
dafasa
6
dDFfSs
6
sfdDSF
6
DFSDFS
3
dfs

输出样例:

0 1
1 1
0 0
1 0
0 1

题目分析

双指针

代码实现

#include <iostream>
using namespace std;
const int N = 100;

int t;
void solve() {
    int n, ai = 0, bi = 0;
    char s[N];
    string a = "DFS", b = "dfs";
    cin >> n >> s + 1;
    for(int i = 1; i <= n; ++i) {
        if(s[i] == a[ai]) ++ai;
        if(s[i] == b[bi]) ++bi;
    }
    cout << (ai > 2) << ' ' << (bi > 2) << '\n';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}
分类: Two Pointers

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status