Tìm và thay thế trong chuỗi C++ (Find And Replace in String)

Cho chuỗi S và các phép thay thế: index i, source x, target y. Nếu x bắt đầu tại i trong S gốc, thay x bằng y. Các phép thay thế độc lập, dựa trên S gốc.

Ví dụ

Input - S="abcd", indexes=[0,2], sources=["a","cd"], targets=["eee","ffff"] Output - "eeebffff"

Giải thích - "a" tại 0 → "eee", "cd" tại 2 → "ffff".

Phương pháp tiếp cận

• Sắp xếp các phép thay thế theo index giảm dần (tránh lệch index khi thay đổi độ dài)
• Duyệt từng phép: nếu S.substr(i, source.size()) == source thì thay thế

Ví dụ code C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
        vector<pair<int, int>> sorted;
        int n = indexes.size();
        for (int i = 0; i < n; i++)
            sorted.push_back({indexes[i], i});
        sort(sorted.rbegin(), sorted.rend());

        for (int j = 0; j < n; j++) {
            int i = sorted[j].first;
            string source = sources[sorted[j].second];
            string target = targets[sorted[j].second];
            if (S.substr(i, source.size()) == source) {
                S = S.substr(0, i) + target + S.substr(i + source.size());
            }
        }
        return S;
    }
};

int main() {
    vector<int> v1 = {0, 2};
    vector<string> v2 = {"a", "cd"};
    vector<string> v3 = {"eee", "ffff"};
    Solution ob;
    cout << ob.findReplaceString("abcd", v1, v2, v3);
    return 0;
}

Kết quả

eeebffff