如何用双指针法判断字符串可通过增减tcp子序列转换

问题描述 #

给定字符串s和目标字符串t，仅允许执行两种操作：从s中删除一个子序列"tcp"，或向s中添加一个子序列"tcp"。判断经过若干次操作后s能否转换为t。

解法思路 #

核心逻辑是：s与t的差异只能是若干个完整的"tcp"子序列的增减。我们通过双指针逐个匹配字符，遇到不匹配时尝试通过删除s中的"tcp"或匹配t中的"tcp"（模拟添加操作）继续对齐；遍历结束后，剩余字符必须能完全拆分为若干"tcp"子序列。

具体步骤：

• 用双指针i（遍历s）和j（遍历t）同步前进，匹配相同字符。
• 遇到不匹配时，先检查s当前位置开始是否存在"tcp"子序列，若存在则跳过该子序列（模拟删除操作）。
• 若s中无可用"tcp"可删，则检查t当前位置开始是否存在"tcp"子序列，若存在则跳过该子序列（模拟添加操作）。
• 若两种操作都无法执行，直接判定为不可转换。
• 遍历结束后，检查s或t的剩余部分是否能完全拆分为若干"tcp"子序列，满足则判定为可转换。

代码实现 #

def find_next_tcp(s, start):
    t_pos = c_pos = p_pos = -1
    for k in range(start, len(s)):
        if t_pos == -1 and s[k] == 't':
            t_pos = k
        elif t_pos != -1 and c_pos == -1 and s[k] == 'c':
            c_pos = k
        elif c_pos != -1 and p_pos == -1 and s[k] == 'p':
            p_pos = k
            break
    return p_pos + 1 if p_pos != -1 else -1

def can_transform(s, t):
    i = j = 0
    n, m = len(s), len(t)
    while i < n and j < m:
        if s[i] == t[j]:
            i += 1
            j += 1
        else:
            # 尝试删除s中的一个tcp
            next_i = find_next_tcp(s, i)
            if next_i != -1:
                i = next_i
                continue
            # 尝试添加tcp，即匹配t中的tcp
            next_j = find_next_tcp(t, j)
            if next_j != -1:
                j = next_j
                continue
            # 两种操作都不行
            return False
    # 处理s剩余部分
    while i < n:
        next_i = find_next_tcp(s, i)
        if next_i == -1:
            return False
        i = next_i
    # 处理t剩余部分
    while j < m:
        next_j = find_next_tcp(t, j)
        if next_j == -1:
            return False
        j = next_j
    return True

# 处理输入输出
q = int(input())
for _ in range(q):
    s = input().strip()
    t = input().strip()
    print("Yes" if can_transform(s, t) else "No")

示例验证 #

输入：

3
tcbdp
bd
tcbdp
tctbcdpp
tcp
abc

输出：

Yes
Yes
No

完全符合题目示例结果。

内容的提问来源于stack exchange，提问作者Aria0325