如何修改C++代码以按字符顺序验证第二个字符串能否组成第一个字符串

你的问题很典型——原来的代码只验证了字符数量匹配，却忽略了字符出现的顺序要求，才会出现UMC和UniverseCeeMake这种数量够但顺序不对却返回Yes的错误。要解决这个问题，我们需要验证第一个字符串是不是第二个字符串的子序列：即第一个字符串的所有字符能按顺序在第二个字符串中找到，不需要连续，但顺序绝对不能乱。

修改思路：双指针法 #

最直观高效的方案是用双指针分别遍历两个字符串，同步跟踪匹配进度：

• 用指针i指向目标字符串（str1）的当前待匹配字符
• 用指针j遍历源字符串（str2），逐个寻找和str1[i]匹配的字符
• 每找到一个匹配字符，就把i往后移一位，继续匹配下一个目标字符
• 如果i能走完str1的所有字符，说明顺序+数量都匹配；如果j遍历完str2但i还没到末尾，说明顺序不匹配

这种方法的时间复杂度是O(m+n)（m、n分别是两个字符串的长度），既满足顺序校验，也适配你设定的字符串长度限制（≤10000）。

修改后的完整代码 #

#include <iostream>
#include <string>
using namespace std;

// 验证str1是否是str2的子序列（同时满足顺序和数量要求）
bool canMakeStrWithOrder(string str1, string str2) {
    int i = 0; // 跟踪str1的待匹配位置
    int j = 0; // 遍历str2的指针
    int len1 = str1.length();
    int len2 = str2.length();
    
    while (i < len1 && j < len2) {
        if (str1[i] == str2[j]) {
            i++; // 匹配成功，推进目标字符串的指针
        }
        j++; // 无论是否匹配，都继续遍历源字符串
    }
    // 若i走完str1，说明所有字符按顺序匹配完成
    return i == len1;
}

int main() {
    int n;
    string str1;
    string str2;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str1 >> str2;
        // 先校验长度是否符合限制
        if (str1.length() <= 10000 && str2.length() <= 10000) {
            if (canMakeStrWithOrder(str1, str2)) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        } else {
            // 长度超出限制时返回No（可根据需求调整）
            cout << "No\n";
        }
    }
    return 0;
}

代码细节说明 #

1. 核心函数canMakeStrWithOrder：

   • 双指针的逻辑确保了str1的字符必须按顺序出现在str2中，完美解决了原代码的顺序漏洞
   • 最终通过i == len1判断所有目标字符是否都按顺序匹配完成

2. main函数优化：

   • 修正了原代码中参数顺序混淆的问题（现在明确str1是需要被组成的目标，str2是源字符串）
   • 补充了长度超出限制时的处理逻辑
   • 输出时添加换行符，让结果展示更清晰

测试示例验证 #

拿你提到的例子UMC和UniverseCeeMake测试：

• 指针i先匹配到str2中的第一个U，i推进到1（对应M）
• 遍历str2到M时，i匹配成功并推进到2（对应C）
• 但此时str2中M之后的字符里已经没有C了，i无法推进到3，最终返回false，输出No，完全符合预期。

内容的提问来源于stack exchange，提问作者bori13