---
tags: leetcode
---

# [833. Find And Replace in String](https://leetcode.com/problems/find-and-replace-in-string/)
---
# My Solution
## The Key Idea for Solving This Coding Question
## C++ Code

struct op {
    string src;
    string tgt;
    op(string &src, string &tgt) : src(src), tgt(tgt) {} 
};

class Solution {
public:
    string findReplaceString(string s, vector<int> &indices, vector<string> &sources, vector<string> &targets) {
        unordered_map<int, op> opHtbl;
        for (int i = 0; i < indices.size(); ++i) {
            opHtbl.insert({indices[i], op(sources[i], targets[i])});
        }

        int sIdx = 0;
        string answer;

        while (sIdx < s.size()) {
            auto iter = opHtbl.find(sIdx);
            if (iter != opHtbl.end()) {
                if (isSubstring(s, iter->second.src, sIdx)) {
                    answer += iter->second.tgt;
                    sIdx += iter->second.src.size();
                } else {
                    answer.push_back(s[sIdx++]);
                }
            } else {
                // sIdx is not in the indices.
                answer.push_back(s[sIdx++]);
            }
        }

        return answer;
    }

private:
    bool isSubstring(string &s, string &src, int sIdx) {
        int srcIdx = 0;
        while (sIdx < s.size() && srcIdx < src.size()) {
            if (s[sIdx] == src[srcIdx]) {
                ++sIdx;
                ++srcIdx;
            } else {
                return false;
            }
        }

        // sIdx >= s.size() is true and srcIdx < src.size() is true  ==> return false
        // sIdx < s.size() is true and srcIdx >= src.size() is true  ==> return true;
        // sIdx >= s.size() is true and srcIdx >= src.size() is true ==> return true;
        if (sIdx >= s.size() && srcIdx < src.size()) {
            return false;
        }
        return true;
    }
};

## Time Complexity
## Space Complexity
# Miscellane
<!--
# Test Cases

"abcd"
[0, 2]
["a", "cd"]
["eee", "ffff"]

"abcd"
[0, 2]
["ab","ec"]
["eee","ffff"]

"vmokgggqzp"
[3,5,1]
["kg","ggq","mo"]
["s","so","bfr"]

-->