首页 > 试题广场 >

？？？

[编程题]？？？
  • 热度指数：1259 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一个字符串 s ，它由小写英文字母和可能是零个或多个的字符 `?` 组成。

旺仔哥哥想将每个 `?` 改成小写英文字母，使字符串 t 成为字符串 s 的子序列（不一定连续）。

输出任何这样的可能的改写后的字符串，如果没有符合条件的字符串存在，则直接报告不可能即可。

输入描述:
第一行包含一个整数 T ( 1 \leq T \leq 10^4 ) - 测试用例数。

每个测试用例的第一行包含一个字符串 s （ 1 \leq |s| \leq 2 \cdot 10^5，且 s 仅由小写英文字母和 ```?``` 组成。

每个测试用例的第二行包含一个字符串 t （ 1 \leq |t| \leq |s| 且 t 仅由小写英文字母组成）--该字符串本应是字符串 s 的子序列。

所有测试用例中 |s| 的总和不超过 2 \cdot 10^5 ，其中 |x| 表示字符串 x 的长度。


输出描述:
对于每个测试用例，如果不存在语句中描述的字符串，则输出 "NO"（不带引号）。

否则，输出 "YES"（不带引号）。然后，输出一行--符合所有条件的字符串。

如果可能有多个答案，您可以输出其中任何一个。
示例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
算法知识视频讲解
添加回答
JavaScript Node
苹果520头像 苹果520
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 双指针思路
void async function () {
    // Write your code here
    var inputArr = [];
    while(line = await readline()){
        inputArr.push(line)
    }
    const num = inputArr[0]
    // 循环很简单，正常理解就行
    // 唯一变化就是i+=2; 即每两个循环一次
    for(let i=1;i<=2*num;i+=2) {
        let s=inputArr[i], t=inputArr[i+1]
        let result = fun(s, t);
        if(result) {
            console.log('YES')
            console.log(result)
        } else {
            console.log('NO')
        }
    }
    function fun(s, t) {
        let j = 0; // 记录子串指针位置
        for(let i=0; i<s.length; i++) {
            // 子串不需要连续，所以只要相等或为'?'都可以替换
            if(s[i] == t[j] || s[i] == '?') {
                s = s.slice(0,i) + t[j] + s.slice(i+1, s.length)
                j+=1
                // 最终子串遍历完才符合条件即可返回
                if(j >= t.length) {
                    s = s.replaceAll('?', 'a')
                    return s;
                }
            }
        }
        return false;
    }
}()

发表于 2026-03-04 17:29:02 回复(0)
提交观点

问题信息

双指针
来自：华为机试编程模拟题3
难度：
1条回答 874浏览

热门推荐

相关试题

？？？

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号