将给定字符串 s 转换为目标字符串 t

Question

您需要将给定字符串s转换为目标字符串t。您只能执行两种操作：从s中删除一个子序列“tcp”或向s添加一个子序列“tcp”。 例如，给定 s 为“tcbdp”，经过一次操作，s可以变成“bd”或“tctbcdpp”。

请判断几次运算后s能否转化为t。

注意：原字符串中子序列的顺序也是从左到右，但它们可能不连续。

输入说明： 第一行包含一个正整数q，代表查询次数。 随后的每一对行代表一个查询：每一行都是一个字符串，分别代表 s 和 t。 1 ≤ q ≤ 10^3 字符串的长度不超过10^3。

输出说明： 输出 q 行，每行包含一个查询的答案。如果s可以转化为t，则输出“Yes”。否则，输出“No”。

示例：

输入

3
tcbdp
bd
tcbdp
tctbcdpp
tcp
abc

输出

Yes
Yes
No

p.s.我知道这个问题可以使用动态规划来解决，但我想知道如何使用两个指针编写算法。

Answer 1

能够添加

tcp

子序列比看起来更强大。例如，您可以将任何

t

、

c

或

p

移动到末尾：

• XtY

  ->

  XtYtcp

  ->

  XYt

• XcY

  ->

  tXcYcp

  ->

  XYc

• XpY

  ->

  tcXpYp

  ->

  XYp

当然，如果您移动所有

t

，然后移动所有

c

，然后移动所有

p

，那么您可以删除所有

tcp

三元组，直到只剩下其中 2 个字母。

如果对两个字符串执行此操作会产生相同的“规范化”结果，则两个字符串是可相互转换的。

同样地，如果两个字符串的

t

、

c

和

p

的计数相差相同的数量，并且它们的 other 字符的子序列相同。

“双指针算法”是遍历两个字符串，跳过并计算

t

、

c

和

p

，同时比较其他字符。