LeetCode 字符串中的查找与替换

对于某些字符串 S，我们将执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。

每个替换操作具有 3 个参数：起始索引 i，源字 x 和目标字 y。规则是如果 x 从原始字符串 S 中的位置 i 开始，那么我们将用 y 替换出现的 x。如果没有，我们什么都不做。

举个例子，如果我们有 S = “abcd” 并且我们有一些替换操作 i = 2，x = “cd”，y = “ffff”，那么因为 “cd” 从原始字符串 S 中的位置 2 开始，我们将用 “ffff” 替换它。

再来看 S = “abcd” 上的另一个例子，如果我们有替换操作 i = 0，x = “ab”，y = “eee”，以及另一个替换操作 i = 2，x = “ec”，y = “ffff”，那么第二个操作将不执行任何操作，因为原始字符串中 S[2] = ‘c’，与 x[0] = ‘e’ 不匹配。

所有这些操作同时发生。保证在替换时不会有任何重叠： S = “abc”, indexes = [0, 1], sources = [“ab”,“bc”] 不是有效的测试用例。

示例 1：

输入：S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"] 输出："eeebffff" 解释： "a" 从 S 中的索引 0 开始，所以它被替换为 "eee"。 "cd" 从 S 中的索引 2 开始，所以它被替换为 "ffff"。

示例 2：

输入：S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"] 输出："eeecd" 解释： "ab" 从 S 中的索引 0 开始，所以它被替换为 "eee"。 "ec" 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

提示：

0 <= indexes.length = sources.length = targets.length <= 100 0 < indexes[i] < S.length <= 1000 给定输入中的所有字符都是小写字母。

$思路分析：$这道题主要是让我们把所给的输入信息进行组合，方便查找。首先我们定义一个结构体MyNode{index，sourceIndex，targetIndex}分别表示起始索引 i，源字 x 和目标字 y。然后我们再将这些结构体按照起始索引index进行递增排序，继而从前完后扫描S串，并进行替换。

//自定义结构：起始索引 i，源字 x 和目标字 y struct MyNode{ int index; int sourceIndex; int targetIndex; MyNode(){} MyNode(int _index, int _sourceIndex, int _targetIndex){ index = _index; sourceIndex = _sourceIndex; targetIndex = _targetIndex; } bool operator< (const MyNode &myNode) const {//重载小于运算符（方便递增排序） return index < myNode.index; } }; class Solution { public: string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) { int indexsSize = indexes.size(); vector<MyNode> hashMap(indexsSize); //第一步：将三个输入的数组信息进行转换 for (int i = 0; i < indexsSize; ++i){ hashMap[i] = MyNode(indexes[i], i, i); } //第二步：按照递增顺序排序hashMap sort(hashMap.begin(), hashMap.end()); string resStr;//存储结果 int strSize = S.size(), strI = 0, hashMapI = 0; //第三步：从前往后扫描S串（并进行替换） while (strI < strSize && hashMapI < indexsSize){ //首先定位到hashMap[hashMapI].index这个替换索引的位置 while (strI < strSize && strI < hashMap[hashMapI].index){ resStr += S[strI++]; } //检查起始索引为strI长度为sources[hashMap[hashMapI].sourceIndex].size()的字符子串是否与sources[hashMap[hashMapI].sourceIndex]相同 if (strI < strSize && S.substr(strI, sources[hashMap[hashMapI].sourceIndex].size()) == sources[hashMap[hashMapI].sourceIndex]){ resStr += targets[hashMap[hashMapI].targetIndex];//替换 strI += sources[hashMap[hashMapI].sourceIndex].size();//跳过S串中刚刚替换的字符段 } hashMapI += 1;//不管有没有替换成功，hashMap的索引都得往后移动 } if (strI < strSize){//最后剩余字符子串放入到尾端 resStr += S.substr(strI); } return resStr; } };