目錄鏈接：

力扣編程題-解法匯總_分享+記錄-CSDN博客

GitHub同步刷題項(xiàng)目：

https://github.com/September26/java-algorithms

原題鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

描述：

你會(huì)得到一個(gè)字符串?s?(索引從 0 開(kāi)始)，你必須對(duì)它執(zhí)行?k?個(gè)替換操作。替換操作以三個(gè)長(zhǎng)度均為?k?的并行數(shù)組給出：indices,?sources,??targets。

要完成第?i?個(gè)替換操作:

1. 檢查?子字符串??sources[i]?是否出現(xiàn)在?原字符串?s?的索引?indices[i]?處。
2. 如果沒(méi)有出現(xiàn)，?什么也不做?。
3. 如果出現(xiàn)，則用?targets[i]?替換?該子字符串。

例如，如果?s = "abcd"?，?indices[i] = 0?,?sources[i] = "ab"，?targets[i] = "eee"?，那么替換的結(jié)果將是?"eeecd"?。

所有替換操作必須?同時(shí)?發(fā)生，這意味著替換操作不應(yīng)該影響彼此的索引。測(cè)試用例保證元素間不會(huì)重疊?。

• 例如，一個(gè)?s = "abc"?，??indices = [0,1]?，?sources = ["ab"，"bc"]?的測(cè)試用例將不會(huì)生成，因?yàn)?"ab"?和?"bc"?替換重疊。

在對(duì)?s?執(zhí)行所有替換操作后返回?結(jié)果字符串?。

子字符串?是字符串中連續(xù)的字符序列。

示例 1：

輸入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
輸出："eeebffff"
解釋：
"a" 從 s 中的索引 0 開(kāi)始，所以它被替換為 "eee"。
"cd" 從 s 中的索引 2 開(kāi)始，所以它被替換為 "ffff"。

示例 2：

輸入：s = "abcd", indices = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
輸出："eeecd"
解釋：
"ab" 從 s 中的索引 0 開(kāi)始，所以它被替換為 "eee"。
"ec" 沒(méi)有從原始的 S 中的索引 2 開(kāi)始，所以它沒(méi)有被替換。

提示：

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indices[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s?僅由小寫(xiě)英文字母組成
• sources[i]?和?targets[i]?僅由小寫(xiě)英文字母組成

解題思路：

* 833. 字符串中的查找與替換

* 解題思路：

* 首先，把indices，sources，targets融合成一個(gè)數(shù)組list，按照indices的大小排序。

* 然后遍歷這個(gè)，嘗試使用list中indices的值去查找，看對(duì)應(yīng)的位置是否匹配，如果匹配，則需要插入兩部分：

* 1.indice之前的部分。

* 2.替換為targets的部分。

* 然后更新index為當(dāng)前位置即可。

* 如果不匹配，則無(wú)需更新，因?yàn)橄麓蔚某晒ζヅ鋾?huì)填充index到當(dāng)前匹配位置所有的值。

代碼：

class Solution833
{
public:string findReplaceString(string s, vector<int> &indices, vector<string> &sources, vector<string> &targets){vector<pair<int, pair<string, string>>> list;for (int i = 0; i < indices.size(); i++){list.push_back(make_pair(indices[i], make_pair(sources[i], targets[i])));}sort(list.begin(), list.end(), [](pair<int, pair<string, string>> pair1, pair<int, pair<string, string>> pair2){ return pair2.first - pair1.first > 0; });string out;int index = 0;for (auto item : list){// 如果相同，則填入替換的string olds = s.substr(item.first, min(item.second.first.size(), s.size() - item.first));if (olds == item.second.first){out.append(s.substr(index, item.first - index));out.append(item.second.second);index = item.first + item.second.first.size();}}out.append(s.substr(index, s.size() - index));return out;}
};