小欧的字符串判定

OPPO 笔试真题 · 2024 秋招 · 研发岗

判题请到牛客原题提交。

题目描述

小欧拿到了两个字符串$s$和$t$，她有一个目标字符串$target$。小欧希望每一位从$s$或者$t$的对应位置的字符中二选一生成$target$，你能告诉小欧她最终能达成目的吗？

输入格式

第一行输入一个正整数$n$，代表$s,t,target$的长度。

第二行输入一个字符串$s$。

第三行输入一个字符串$t$。

第四行输入一个字符串$target$。

$1\leq n \leq 100$

输出格式

如果可以达成目的，则输出"Yes"。否则输出"No"

示例

示例 1

输入：

3
abc
bad
aac

输出：

Yes

说明：

第一个、第三个字符取$s$的、第二个字符取$t$的即可。

示例 2

输入：

2
ab
bb
aa

输出：

No

说明：

第二个字符无论取$s$还是取$t$，都无法得到字符'a'。

---

解题思路

第一步：理解问题本质

target 的第 i 位只能从 s[i] 或 t[i] 里选。
注意每一位是各自独立的：第 1 位选了 s 的字符，并不会限制第 2 位能不能选 t。
题目也没有「s 和 t 各自只能用多少次」的限制。

第二步：把「能否达成」化成逐位条件

既然每一位互不影响，那么「存在一种选择方案」就等价于
「每一位都存在至少一种选择」。用逻辑与把它们连起来：

能达成  ⇔  target[0] ∈ {s[0], t[0]}
        ∧  target[1] ∈ {s[1], t[1]}
        ∧  ...
        ∧  target[n-1] ∈ {s[n-1], t[n-1]}

只要有一位两个候选都不等于目标字符，这一位无论怎么选都失败，整题就是 No。

第三步：实现

从下标 0 扫到 n-1，每一位检查 target[i] 是否等于 s[i] 或 t[i]。
遇到不满足的直接输出 No 并返回，省掉后面的检查；全部通过则输出 Yes。

---

完整代码实现

import sys


def solve() -> None:
    """逐位判断 target[i] 是否在 {s[i], t[i]} 中"""
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    s, t, target = data[1], data[2], data[3]
    for i in range(n):
        if target[i] != s[i] and target[i] != t[i]:
            sys.stdout.write("No\n")
            return
    sys.stdout.write("Yes\n")


if __name__ == "__main__":
    solve()

---

示例推演

示例 1：n = 3，s = "abc"，t = "bad"，target = "aac"。

位置 i	s[i]	t[i]	候选集合	target[i]	是否可行
0	a	b	{a, b}	a	可行，取 s
1	b	a	{b, a}	a	可行，取 t
2	c	d	{c, d}	c	可行，取 s

三位全部可行，输出 Yes。对应的选择是「s、t、s」。

示例 2：n = 2，s = "ab"，t = "bb"，target = "aa"。

位置 i	s[i]	t[i]	候选集合	target[i]	是否可行
0	a	b	{a, b}	a	可行
1	b	b	{b}	a	不可行

第 1 位两个候选都是 b，凑不出 a，输出 No。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
逐位检查	O(n)	O(1)	每一位只看两个字符，推荐
枚举所有 2^n 种选择	O(2^n · n)	O(n)	n 可达 100，不可行

---

易错点总结

1. 输出的大小写

题目要求 Yes / No，首字母大写、其余小写，不是 YES / NO。

2. 把独立选择想成有约束的选择

每一位之间没有任何关联，不需要回溯，也不存在「前面选了 s，后面就得选 t」这样的规则。
直接逐位比较就够了。

3. 输入里有 n，但不要用它去截断字符串

n 只是长度说明，s、t、target 本身已经读进来了。
循环用 range(n) 或 range(len(s)) 都可以。

4. 注意 and 与 or 的搭配

「既不等于 s[i] 也不等于 t[i]」才失败，条件要写成
target[i] != s[i] and target[i] != t[i]。写成 or 会把只要有一边不同的位置全部判失败。

---

扩展思考

• 如果再加一个限制「s 和 t 各只能用 n/2 次」，逐位判断就不够了，
  需要统计「只能取 s 的位置数」和「只能取 t 的位置数」是否超过配额。
• 如果题目改成「能否通过重排 s 得到 target」，就变成字符计数问题（比较两种字母频次）。
• 这类「每一位独立、答案取逻辑与」的判定题，通常都能在 O(n) 内解决，
  不需要搜索或动态规划。

---

相关题目

• 小欧的字符交换