AtCoder Beginner Contest 259 - C - XX to XXX

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

You are given two strings SS and TT. Determine whether it is possible to make SS equal TT by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in SS, insert a character equal to these characters. That is, take the following three steps.

  1. Let NN be the current length of SS, and S=S1S2SNS = S_1S_2\ldots S_N.
  2. Choose an integer ii between 11 and N1N-1 (inclusive) such that Si=Si+1S_i = S_{i+1}. (If there is no such ii, do nothing and terminate the operation now, skipping step 3.)
  3. Insert a single copy of the character Si(=Si+1)S_i(= S_{i+1}) between the ii-th and (i+1)(i+1)-th characters of SS. Now, SS is a string of length N+1N+1: S1S2SiSiSi+1SNS_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

  • Each of SS and TT is a string of length between 22 and 2×1052 \times 10^5 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

SS
TT
TEXT

Output

If it is possible to make SS equal TT, print Yes; otherwise, print No. Note that the judge is case-sensitive.


Sample Input 1

abbaac
abbbbaaac
TEXT

Sample Output 1

Yes
TEXT

You can make S=S = abbaac equal T=T = abbbbaaac by the following three operations.

  • First, insert b between the 22-nd and 33-rd characters of SS. Now, S=S = abbbaac.
  • Next, insert b again between the 22-nd and 33-rd characters of SS. Now, S=S = abbbbaac.
  • Lastly, insert a between the 66-th and 77-th characters of SS. Now, S=S = abbbbaaac.

Thus, Yes should be printed.


Sample Input 2

xyzz
xyyzz
TEXT

Sample Output 2

No
TEXT

No sequence of operations makes S=S = xyzz equal T=T = xyyzz. Thus, No should be printed.

题目大意

你可以在字符串S的连续两个相同的字母变成连续且相同的三个字母

通俗地讲,就是..aa.能变成..aaa.

问你S串能否变成T

解题思路

用双指针分别记录ST处理到了那个字母。(分别记为locSlocT

如果ST对应的字母相同,则两个指针分别向后移动一位

1
2
if (S[locS] == T[locT])
locS++, locT++;
CPP

否则(ST对应的元素不同),要想使得S变成T就需要在S中插入一个字母T[locT]

要想在SlocS处插入一个字母T[locT],就需要S[loc1]S[loc2]都为T[locT]。(因为已知S[locS]T[locT],所以新插入的字母不可能通过S[locS]S[locS+1]拓展出来)

  • 如果S[loc1]S[loc2]都为T[locT],就locT++TlocT已由S[loc1]S[loc2]拓展出来)
  • 否则,直接输出No并结束即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

#define Yes {puts("Yes"); return 0;}
#define No {puts("No"); return 0;}

int main() {
string s, t;
cin >> s >> t;
int locs = 0, loct = 0;
while (locs < s.size() || loct < t.size()) {
if (loct >= t.size()) {
No;
}
if (locs < s.size() && s[locs] == t[loct]) {
locs++, loct++;
}
else {
if (locs - 2 >= 0 && s[locs - 1] == t[loct] && s[locs - 2] == t[loct]) {
loct++;
}
else {
No;
}
}
}
if (loct == t.size()) {
Yes;
}
else {
No;
}
return 0;
}
CPP

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/125700254


AtCoder Beginner Contest 259 - C - XX to XXX
https://blog.letmefly.xyz/2022/07/09/AtCoder Beginner Contest 259 - C - XX to XXX/
作者
发布于
2022年7月9日
许可协议