需要做個(gè)網(wǎng)站長(zhǎng)沙有實(shí)力的關(guān)鍵詞優(yōu)化價(jià)格
目錄鏈接:
力扣編程題-解法匯總_分享+記錄-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è)替換操作:
- 檢查?子字符串??
sources[i]
?是否出現(xiàn)在?原字符串?s
?的索引?indices[i]
?處。 - 如果沒(méi)有出現(xiàn),?什么也不做?。
- 如果出現(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;}
};