问题描述
p10340原题链接:UVaOJ 10340 - All in Alls
相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-9
解法一:双指针
只要 s 是 t 的题目描述的子串,那么对任意的 $s_{i}$ 和 $s_{j}$, 其中 $i <j$; 一定存在 $p < q$, 满足 $t_{p} < t{q}$. 根据顺序特性,使用两个指针对字符串进行扫描,看最终 s 中的所有字符能否在 t 中顺序出现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <bits/stdc++.h> using namespace std; int main() { string s, t; while (cin >> s >> t) { int p1 = 0, p2 = 0; while (p1 < s.length() && p2 < t.length()) s[p1] == t[p2] ? p1++, p2++ : p2++; cout << (p1 == s.length() ? "Yes" : "No") << endl; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 |
while True: try: s, t = input().split() p1 = p2 = 0 while (p1 < len(s) and p2 < len(t)): if s[p1] == t[p2]: p1 += 1 p2 += 1 print("Yes" if p1 == len(s) else "No") except EOFError: break |