P76012 子序列问候 — 题解

专题： 字符串
适用题目： 新生 OJ 本地题包中的 P76012，不要直接用于外站同名题。

解题思路

用指针 j 指向目标串 hello 中尚未匹配的下一个字符，顺序扫描原串。

复杂度

时间 $O(n)$，额外空间 $O(1)$。

易错点

子序列允许跳过字符，但 hello 中的两个 l 必须分别匹配。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    static char s[100005]; const char *target = "hello";
    scanf("%100004s", s);
    int j = 0;
    for (int i = 0; s[i] && j < 5; i++) if (s[i] == target[j]) j++;
    puts(j == 5 ? "YES" : "NO");
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s,t="hello";
    cin>>s;
    int j=0;
    for(char c:s)if(j<5&&c==t[j])j++;
    cout<<(j==5?"YES":"NO")<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。