华为 · 双指针 · 算法编程题
华为 双指针 T ≤ 1e4 时限 1 秒 / 256 MB

题目描述

有一个字符串 s ，它由小写英文字母和可能是零个或多个的字符 `?` 组成。
旺仔哥哥想将每个 `?` 改成小写英文字母，使字符串 t 成为字符串 s 的子序列（不一定连续）。
输出任何这样的可能的改写后的字符串，如果没有符合条件的字符串存在，则直接报告不可能即可。

输入输出

输入描述
第一行包含一个整数 T ( 1 ≤ T ≤ 10^4 ) - 测试用例数。
每个测试用例的第一行包含一个字符串 s （ 1 ≤ |s| ≤ 2 · 10^5 ，且 s 仅由小写英文字母和 ```?``` 组成。
每个测试用例的第二行包含一个字符串 t （ 1 ≤ |t| ≤ |s| 且 t 仅由小写英文字母组成）--该字符串本应是字符串 s 的子序列。
所有测试用例中 |s| 的总和不超过 2 · 10^5 ，其中 |x| 表示字符串 x 的长度。
输出描述
对于每个测试用例，如果不存在语句中描述的字符串，则输出 "NO"（不带引号）。
否则，输出 "YES"（不带引号）。然后，输出一行--符合所有条件的字符串。
如果可能有多个答案，您可以输出其中任何一个。

样例共 1 组

样例 1
输入
4
??a???e????ba
efe
cbe??????e?b???b
be
a???bf?????
deadaeefb
f???bf?efc?eeebac?
afbacea
输出
YES
efaeaaeaaaaba
YES
cbeaaaaaaeabaaab
NO
YES
fafbbfaefceeeebaca

算法解析依据充分

考点：双指针

数据规模 T ≤ 1e4 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：T ≤ 1e4
  • 元素值域：s ≤ 2（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：双指针

用两个指针协同移动，把两层循环的 O(n²) 优化到 O(n)。

思路框架（双指针 通法 · 非本题专属）

  1. 判断是「对撞指针」（一左一右向中间靠拢）还是「快慢指针」（同向不同速）。
  2. 确定指针移动的单调条件：什么情况下移动左指针，什么情况下移动右指针。
  3. 每一步根据当前指针位置更新答案，直到指针相遇或越界。
  4. 常配合有序性使用：无序时先排序。

实现要点：写成 while (l < r) 循环最清晰，切记每轮至少有一个指针移动，否则死循环。

复杂度：时间 O(n)（排序则 O(n log n)） ｜ 空间 O(1)

该范式的通法易错点

  • 指针移动条件写反，漏解或死循环。
  • 两指针同时移动导致跳过合法解。

对照本题

  • 数据规模 T ≤ 1e4，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 2 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：4 / ??a???e????ba / efe / cbe??????e?b???b / be / a???bf????? / deadaeefb / f???bf?efc?eeebac? / afbacea
  • 输出：YES / efaeaaeaaaaba / YES / cbeaaaaaaeabaaab / NO / YES / fafbbfaefceeeebaca

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：华为机试编程模拟题3。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解