题解 | #？？？#

题目链接

题目描述

给定一个由小写英文字母和 '?' 组成的字符串 $s_1$ ，以及一个只由小写英文字母组成的字符串 $s_2$ 。

任务是将 $s_1$ 中的每一个 '?' 替换成一个小写英文字母，使得 $s_2$ 是替换后 $s_1$ 的一个子序列。

如果存在这样的构造方式，输出 "YES" 和任意一个构造后的 $s_1$ ；如果不存在，则输出 "NO"。

解题思路

这是一个子序列匹配问题，可以采用贪心算法来解决。一个非常有效的策略是从右向左进行匹配。

核心思想：为了最大化匹配成功的可能性，我们应该为 $s_2$ 中的每个字符在 $s_1$ 中寻找尽可能靠右的位置。例如，对于 $s_2$ 的最后一个字符，如果我们在 $s_1$ 中选择最右边的可能位置来匹配它，那么 $s_2$ 的其余前缀部分将拥有最长的 $s_1$ 前缀来进行匹配。

算法步骤：

我们使用两个指针， $p_1$ 指向字符串 $s_1$ 的末尾， $p_2$ 指向字符串 $s_2$ 的末尾。
我们将字符串 $s_1$ 转换为一个字符数组，以便进行修改。
我们从后向前遍历 $s_1$ 的字符数组（即 $p_1$ 从 $n-1$ 递减到 $0$ ）。
在当前位置 $p_1$ ：
- 检查是否仍然需要匹配 $s_2$ 中的字符（即 $p_2 \ge 0$ ），以及当前字符 $s_1[p_1]$ 是否能与 $s_2[p_2]$ 匹配。匹配的条件是 $s_1[p_1] == s_2[p_2]$ 或者 $s_1[p_1] == '?'$ 。
- 如果可以匹配，我们就确定这个匹配。我们将 $s_1$ 字符数组在 $p_1$ 位置的字符更新为 $s_2[p_2]$ ，并将指针 $p_2$ 向左移动一位，表示 $s_2$ 的这个字符已经成功匹配。
- 如果不能匹配，或者 $p_2$ 已经小于 0（意味着 $s_2$ 已全部匹配完），我们就处理 $s_1[p_1]$ 的填充。如果 $s_1[p_1]$ 是一个 '?'，为了构造一个确定的答案，我们统一将其替换为 'a'。
当 $p_1$ 遍历完整个 $s_1$ 后，我们检查 $p_2$ 的最终位置。
- 如果 $p_2 < 0$ ，说明 $s_2$ 的所有字符都找到了匹配位置，构造成功。输出 "YES" 和修改后的字符串。
- 如果 $p_2 \ge 0$ ，说明 $s_1$ 遍历结束后仍有 $s_2$ 的字符未能匹配，构造失败。输出 "NO"。

这个算法通过一次从右到左的遍历，同时完成了可行性判断和结果构造，时间复杂度是线性的。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    string s1, s2;
    cin >> s1 >> s2;
    int n = s1.length();
    int m = s2.length();

    int p1 = n - 1;
    int p2 = m - 1;

    while (p1 >= 0) {
        if (p2 >= 0 && (s1[p1] == s2[p2] || s1[p1] == '?')) {
            s1[p1] = s2[p2];
            p2--;
        } else if (s1[p1] == '?') {
            s1[p1] = 'a';
        }
        p1--;
    }

    if (p2 < 0) {
        cout << "YES" << endl;
        cout << s1 << endl;
    } else {
        cout << "NO" << endl;
    }
}

int main() {
    // 多组测试数据，总输入量较大，建议使用关流语句
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    private static void solve(Scanner sc) {
        String s1_str = sc.next();
        String s2_str = sc.next();
        char[] s1 = s1_str.toCharArray();
        char[] s2 = s2_str.toCharArray();
        int n = s1.length;
        int m = s2.length;

        int p1 = n - 1;
        int p2 = m - 1;

        while (p1 >= 0) {
            if (p2 >= 0 && (s1[p1] == s2[p2] || s1[p1] == '?')) {
                s1[p1] = s2[p2];
                p2--;
            } else if (s1[p1] == '?') {
                s1[p1] = 'a';
            }
            p1--;
        }

        if (p2 < 0) {
            System.out.println("YES");
            System.out.println(new String(s1));
        } else {
            System.out.println("NO");
        }
    }
}

import sys

def solve():
    s1 = list(sys.stdin.readline().strip())
    s2 = list(sys.stdin.readline().strip())
    n = len(s1)
    m = len(s2)

    p1 = n - 1
    p2 = m - 1

    while p1 >= 0:
        if p2 >= 0 and (s1[p1] == s2[p2] or s1[p1] == '?'):
            s1[p1] = s2[p2]
            p2 -= 1
        elif s1[p1] == '?':
            s1[p1] = 'a'
        p1 -= 1
    
    if p2 < 0:
        print("YES")
        print("".join(s1))
    else:
        print("NO")

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心算法 + 双指针。
时间复杂度： $O(\sum |s_1|)$ 。对于每个测试用例，我们都对字符串 $s_1$ 进行一次线性扫描，总时间复杂度是所有测试用例中 $s_1$ 长度的总和。
空间复杂度： $O(\sum |s_1|)$ 。主要是存储所有输入的字符串。在单个测试用例中，需要 $O(|s_1|)$ 的空间来存储字符数组。