[LeetCode]Find And Replace in String

很简单的题目，因为replace的部分是没有overlap的，我们只需要记录对于原string s的第i位，有没有从i位开始合法的replace string。最后我们从头扫一遍每个index重构新的string即可。时间复杂度O(n + m)，n为输入s的长度，m为所有replace string的长度。

	class Solution {
	public:
	string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
	int len = S.size(), n = indexes.size();
	vector<int> mapping(len, -1);
	for (int i = 0; i < n; ++i)
	{
	int subLen = sources[i].size(), idx = indexes[i];
	if (S.substr(idx, subLen) == sources[i])mapping[idx] = i;
	}
	int idx = 0;
	string res;
	while (idx < len)
	{
	if (mapping[idx] != -1)
	{
	int i = mapping[idx];
	res += targets[i];
	idx += sources[i].size();
	}
	else
	res += S[idx++];
	}
	return res;
	}
	};

view raw Find And Replace in String.cpp hosted with ❤ by GitHub