首页 > 试题广场 >

？？？

[编程题]？？？

热度指数：896 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个字符串 $s$ ，它由小写英文字母和可能是零个或多个的字符 `?` 组成。

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

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

输入描述:

第一行包含一个整数  (  ) - 测试用例数。

每个测试用例的第一行包含一个字符串  （ ，且  仅由小写英文字母和 ```?``` 组成。

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

所有测试用例中  的总和不超过  ，其中  表示字符串  的长度。

输出描述:

对于每个测试用例，如果不存在语句中描述的字符串，则输出 "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

算法知识视频讲解

C++

想当offer收割机的咸鱼很想吃卤蛋

有一个简单的基于贪心的O(N)方法。主要思路是，用一个指针head指示t中已匹配的位置，依次遍历s中字符，如果是问号则直接用于匹配t中head指向字符；如果是相等则正好匹配。这里主要是要想明白为什么可以遇到问号就能用于匹配。例如假设s为"?ab"，t为"ab"，看上去似乎直接匹配两者的ab即可，无需用问号，但是实际上用问号也不会影响后续的正确匹配，相当于是用一个问号代替了后续的某个具体字符的匹配。代码如下：

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    cin.ignore();
    for (int ti=0; ti<t; ++ti) {
        string ss,st;
        getline(cin, ss);
        getline(cin, st);
        int ht = 0;
        
        string ans = ss;
        for (int i=0; i<ss.size(); ++i) {
            if (ht<st.size()) {
                if (ss[i]=='?' || ss[i]==st[ht]) {
                    ans[i]  = st[ht];
                    ht += 1;
                }
            }
            else {
                if (ss[i]=='?') ans[i]='a';
            }
        }

        if (ht!=st.size()) cout << "NO" << endl; else {
            cout << "YES" << endl << ans << endl;
        }


    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-10-11 17:11:48 回复(0)

牛客487544150号

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        string s,t;
        cin >> s >> t;
        int tLeftIndex = 0;
        int tRightIndex = 0;
        for (int j = 0; j < s.size(); j++) {
            if (tLeftIndex < t.size()) {
                if (s[j] == '?') {
                    s[j] = t[tLeftIndex];
                    tLeftIndex++;
                } else {
                    if (s[j] == t[tLeftIndex]) {
                        tLeftIndex++;
                    }
                }
            } else {
                if (s[j] == '?') {
                    s[j] = 'a';
                }
            }
        }
        if (tLeftIndex == t.size()) {
            cout << "YES" << endl;
            cout << s << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

发表于 2025-12-13 18:20:40 回复(0)

Python3

牛客341639822号

import re
n = int(input()) for num in range(n):
    s = input()
    t = input()
    find = re.findall(r'\?+', s)
    length = sum(len(i) for i in find)
    total = 0  for i in t:
        total += s.count(i) if length >= len(t): print('YES')
        t = t + 'a' * (length - len(t))
        left = 0  right = 0  while len(s) > right: if s[right] == '?':
                s = s.replace(s[right], t[left], 1)
                left += 1  right += 1  print(s) elif s.count('?') + total >= len(t):
        left = 0  right = 0  flag = 'NO'  while len(s) > right: if s[right] == t[left]:
                left += 1  elif s[right] == '?' and left < len(t):
                s = s.replace(s[right], t[left], 1)
                left += 1  if left == len(t):
                flag = 'YES'  break  right += 1  print(flag) if flag == 'YES': if s.count('?') != 0:
                s = s.replace('?', 'a') print(s) else: print('NO')

发表于 2025-10-02 19:06:13 回复(0)

晴天emo雨天high

import sys
a = [ i.replace('\n','') for i in list(sys.stdin)]
n = int(a[0])
a.pop(0)

for i in range(n):
    if len(a[2*i+1]) > len(a[2*i]):
        print("NO")
    else:
        x = list()
        for n in a[2*i]:
            count = 0
            if len(a[2*i+1]) > 0:
                for j in a[2*i+1]:
                    if n =="?":
                        x.append(j)
                        a[2*i+1] = a[2*i+1][1:]
                        break
                    elif n == j:
                        x.append(j)
                        a[2*i+1] = a[2*i+1][1:]
                        break
                    else:
                        x.append(n)
                        break
            else:
                if n =="?":
                    x.append("a")
                else:
                    x.append(n)
    if len(x)>len(a[2*i])&nbs***bsp;len(a[2*i+1])>0:
        print("NO")
    else:
        print("YES")
        print("".join(x))

发表于 2025-09-12 22:44:53 回复(0)

提交观点

问题信息

双指针

来自：华为机试编程模拟题3

难度：

4条回答 13收藏 495浏览

？？？

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题