题解 | #？？？#

题目链接

题目描述

给定一个字符串 $s$ ，它由小写英文字母和若干个 '?' 字符组成。另外给定一个字符串 $t$ ，它只由小写英文字母组成。你需要将 $s$ 中的每一个 '?' 替换成一个小写英文字母，使得字符串 $t$ 成为新字符串 $s'$ 的一个子序列。

请输出任意一个满足条件的字符串 $s'$ ；如果不存在这样的字符串，则输出 "NO"。

输入:

第一行是一个整数 $T$ ，表示测试用例的数量。
每个测试用例包含两行：
- 第一行是字符串 $s$ ( $1 \le |s| \le 2 \cdot 10^5$ )。
- 第二行是字符串 $t$ ( $1 \le |t| \le |s|$ )。
所有测试用例中 $|s|$ 的总和不超过 $2 \cdot 10^5$ 。

输出:

对每个测试用例，如果存在解，则先输出 "YES"，然后换行输出构造好的字符串 $s'$ 。
如果不存在解，则输出 "NO"。

解题思路

本题要求我们将字符串 $s$ 中的 '?' 替换成小写字母，使得字符串 $t$ 成为新字符串 $s'$ 的子序列。由于 $|s|$ 的总和很大， $\mathcal{O}(|s| \cdot |t|)$ 的动态规划会超时。我们需要一个更线性的方法。

我们可以分两步解决：首先判断是否存在解，然后构造一个解。

1. 判断可行性 (双向贪心扫描)

一个解存在的充要条件是，对于 $t$ 中的任意相邻两个字符 $t_j$ 和 $t_{j+1}$ ，我们能在 $s$ 中找到一对匹配位置 $i_j < i_{j+1}$ 。为了保证这对位置总是存在，我们需要确保为 $t_j$ 选择的最早匹配位置 严格小于 为 $t_{j+1}$ 选择的最晚匹配位置。

这启发我们进行两次扫描：

从左到右扫描：我们计算一个数组 left_match，其中 left_match[j] 表示为了形成子序列 t[0...j]，t[j] 在 $s$ 中能匹配的最早（最靠左）的索引。这可以通过一次对 $s$ 和 $t$ 的贪心扫描来完成。
从右到左扫描：类似地，我们计算数组 right_match，其中 right_match[j] 表示为了形成子序列 t[j...m-1]，t[j] 在 $s$ 中能匹配的最晚（最靠右）的索引。

在计算完这两个数组后，我们检查是否存在解。一个解存在当且仅当： a. 两次扫描都能成功匹配 $t$ 的所有字符。 b. 对于所有的 $j$ from $0$ to $|t|-2$ ，都满足 left_match[j] < right_match[j+1]。

2. 构造解 (单向贪心)

一旦确认有解，我们可以用一个简单的从左到右的贪心策略来构造结果：

将 $s$ 转换为字符数组。遍历字符串 $s$ ，同时用一个指针 t_ptr 指向 $t$ 中当前需要匹配的字符 t[t_ptr]。
当我们遍历到 s[i] 时，如果 s[i] 可以匹配 t[t_ptr]，我们就进行这个匹配。我们将 s[i]（如果为 '?'）替换为 t[t_ptr]，然后将 t_ptr 向后移动一位。
所有未被用于匹配 $t$ 的 '?' 字符，都可以安全地替换为任意字母（如 'a'）。
最后将构造好的字符数组转换为字符串并输出。

这个算法的每一步都是线性扫描，总时间复杂度为 $\mathcal{O}(|s| + |t|)$ ，满足题目要求。

代码

cpp
java
python

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

using namespace std;

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

    vector<int> left_match(m);
    int s_ptr = 0;
    for (int i = 0; i < m; ++i) {
        while (s_ptr < n && (s[s_ptr] != t[i] && s[s_ptr] != '?')) {
            s_ptr++;
        }
        if (s_ptr == n) {
            cout << "NO" << endl;
            return;
        }
        left_match[i] = s_ptr;
        s_ptr++;
    }

    vector<int> right_match(m);
    s_ptr = n - 1;
    for (int i = m - 1; i >= 0; --i) {
        while (s_ptr >= 0 && (s[s_ptr] != t[i] && s[s_ptr] != '?')) {
            s_ptr--;
        }
        if (s_ptr < 0) {
            cout << "NO" << endl;
            return;
        }
        right_match[i] = s_ptr;
        s_ptr--;
    }

    for (int i = 0; i < m - 1; ++i) {
        if (left_match[i] >= right_match[i + 1]) {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
    vector<char> result(s.begin(), s.end());
    s_ptr = 0;
    for (int i = 0; i < m; ++i) {
        while (s_ptr < n && (s[s_ptr] != t[i] && s[s_ptr] != '?')) {
            if (result[s_ptr] == '?') result[s_ptr] = 'a';
            s_ptr++;
        }
        result[s_ptr] = t[i];
        s_ptr++;
    }
    while(s_ptr < n) {
        if (result[s_ptr] == '?') result[s_ptr] = 'a';
        s_ptr++;
    }
    
    for(char c : result) cout << c;
    cout << 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);
        }
    }

    public static void solve(Scanner sc) {
        String s = sc.next();
        String t = sc.next();
        int n = s.length();
        int m = t.length();

        int[] leftMatch = new int[m];
        int sPtr = 0;
        for (int i = 0; i < m; i++) {
            while (sPtr < n && s.charAt(sPtr) != t.charAt(i) && s.charAt(sPtr) != '?') {
                sPtr++;
            }
            if (sPtr == n) {
                System.out.println("NO");
                return;
            }
            leftMatch[i] = sPtr;
            sPtr++;
        }

        int[] rightMatch = new int[m];
        sPtr = n - 1;
        for (int i = m - 1; i >= 0; i--) {
            while (sPtr >= 0 && s.charAt(sPtr) != t.charAt(i) && s.charAt(sPtr) != '?') {
                sPtr--;
            }
            if (sPtr < 0) {
                System.out.println("NO");
                return;
            }
            rightMatch[i] = sPtr;
            sPtr--;
        }

        for (int i = 0; i < m - 1; i++) {
            if (leftMatch[i] >= rightMatch[i + 1]) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
        char[] result = s.toCharArray();
        sPtr = 0;
        for (int i = 0; i < m; i++) {
            while (sPtr < n && s.charAt(sPtr) != t.charAt(i) && s.charAt(sPtr) != '?') {
                if (result[sPtr] == '?') result[sPtr] = 'a';
                sPtr++;
            }
            result[sPtr] = t.charAt(i);
            sPtr++;
        }
        while (sPtr < n) {
            if (result[sPtr] == '?') result[sPtr] = 'a';
            sPtr++;
        }
        System.out.println(new String(result));
    }
}

def solve():
    s = input()
    t = input()
    n, m = len(s), len(t)

    left_match = [-1] * m
    s_ptr = 0
    for i in range(m):
        while s_ptr < n and s[s_ptr] != t[i] and s[s_ptr] != '?':
            s_ptr += 1
        if s_ptr == n:
            print("NO")
            return
        left_match[i] = s_ptr
        s_ptr += 1
    
    right_match = [-1] * m
    s_ptr = n - 1
    for i in range(m - 1, -1, -1):
        while s_ptr >= 0 and s[s_ptr] != t[i] and s[s_ptr] != '?':
            s_ptr -= 1
        if s_ptr < 0:
            print("NO")
            return
        right_match[i] = s_ptr
        s_ptr -= 1

    for i in range(m - 1):
        if left_match[i] >= right_match[i + 1]:
            print("NO")
            return
            
    print("YES")
    result = list(s)
    s_ptr = 0
    for i in range(m):
        while s_ptr < n and s[s_ptr] != t[i] and s[s_ptr] != '?':
            if result[s_ptr] == '?':
                result[s_ptr] = 'a'
            s_ptr += 1
        result[s_ptr] = t[i]
        s_ptr += 1
    
    while s_ptr < n:
        if result[s_ptr] == '?':
            result[s_ptr] = 'a'
        s_ptr += 1

    print("".join(result))

T = int(input())
for _ in range(T):
    solve()

算法及复杂度

算法：双向贪心扫描 + 构造
时间复杂度： $\mathcal{O}(|s| + |t|)$ 。可行性判断和构造解都只需要对字符串进行常数次线性扫描。
空间复杂度： $\mathcal{O}(|s| + |t|)$ ，主要用于存储 left_match、right_match 数组以及结果字符串。