小欧的字符串判定
小欧的字符串判定
OPPO 笔试真题 · 牛客原题
题目描述
小欧拿到了两个字符串 s 和 t,她有一个目标字符串 target。小欧希望每一位从 s 或者 t 的对应位置中二选一生成 target,你能告诉她最终能达成目的吗?
输入格式
第一行输入一个正整数 n,代表 s、t、target 的长度。
接下来三行依次是字符串 s、t、target。
1 <= n <= 100
输出格式
可以达成则输出 Yes,否则输出 No。
示例
示例 1
输入:
3
abc
bad
aac输出:
Yes说明: 第 1、3 位取 s 的 a、c,第 2 位取 t 的 a,拼出 aac。
示例 2
输入:
2
ab
bb
aa输出:
No说明: 第 2 位要的是 a,而 s[1] 和 t[1] 都是 b,两边都取不到。
解题思路
每一位的选择互不影响——第 i 位取 s[i] 还是 t[i],和别的位怎么取没有关系。所以判定退化成一句:每一位都必须能从 {s[i], t[i]} 里选出 target[i],中间只要有一位选不出就整体失败。
逐位检查,提前返回
for i in range(n):
if target[i] != s[i] and target[i] != t[i]:
return "No"
return "Yes"失败条件是「target[i] 既不等于 s[i] 也不等于 t[i]」,两个比较之间是 and——两边都不是,这一位才真的取不到。写成 or 会变成「只要有一边不同就失败」,几乎每个串都会被判成 No。
不需要枚举 2^n 种取法:每一位独立,全部满足就是可行解,这就是全部证明。
推演:示例 1
s = "abc"、t = "bad"、target = "aac"。
| 位 | s[i] | t[i] | target[i] | 能取到? |
|---|---|---|---|---|
| 0 | a | b | a | 是(取 s) |
| 1 | b | a | a | 是(取 t) |
| 2 | c | d | c | 是(取 s) |
三位全过,输出 Yes。示例 2 在第 1 位就停下:s[1] = t[1] = 'b',而目标是 'a',两边都取不到,输出 No。
完整代码实现
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
s, t, target = data[1].decode(), data[2].decode(), data[3].decode()
for i in range(n):
# 两边都取不到 target[i],这一位就补不上
if target[i] != s[i] and target[i] != t[i]:
sys.stdout.write("No")
return
sys.stdout.write("Yes")
if __name__ == "__main__":
solve()复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 逐位检查(最优) | O(n) | O(1) | 每一位只比较两次,第一位失败就返回 |
枚举 2^n 种取法 | O(2^n · n) | O(n) | n = 100 时是天文数字,且没有必要 |
易错点总结
1. 失败条件把 and 写成 or
if target[i] != s[i] or target[i] != t[i] 的意思是「只要有一边不同就失败」,而每一位几乎总会有一边不同。示例 1 的 i = 0:目标 a 等于 s[0],却不等于 t[0] = 'b',or 立刻返回 No,正确答案是 Yes。判据是「两边都对不上」。
扩展思考
- 若每一位可以取
s[i]、t[i]之外的字符(比如还允许一个通配串u),判定条件扩成三元组即可,仍然是逐位独立。 - 若问「至少改几个字符才能让
target可由s、t生成」,就变成逐位计数:两边都对不上的位数就是答案。