833.字符串中的查找与替换

链接：833.字符串中的查找与替换
难度：Medium
标签：数组、哈希表、字符串、排序
简介：在对 s 执行所有替换操作后返回 结果字符串 。

题解 1 - cpp

• 编辑时间：2023-08-15
• 执行用时：8ms
• 内存消耗：13.16MB
• 编程语言：cpp
• 解法介绍：从后往前遍历。

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = indices.size();
        vector<int> idxs;
        for (int i = 0; i < n; i++) idxs.push_back(i);
        sort(idxs.begin(), idxs.end(), [&](auto &i1, auto &i2) {
            return indices[i2] < indices[i1];
        });
        auto check = [&](int &start, string &source) {
            for (int i = 0; i < source.size(); i++) {
                if (start + i >= s.size() || source[i] != s[start + i]) return false;
            }
            return true;
        };
        for (int idx = 0; idx < n; idx++) {
            int i = idxs[idx];
            if (check(indices[i], sources[i])) {
                s = s.substr(0, indices[i]) + targets[i] + s.substr(indices[i] + sources[i].size());
            }
        }
        return s;
    }
};

题解 2 - python

• 编辑时间：2023-08-15
• 执行用时：44ms
• 内存消耗：16.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        n = len(indices)
        idxs = [i for i in range(n)]
        idxs.sort(key=lambda i: indices[i], reverse=True)
        for idx in range(n):
            i = idxs[idx]
            if s[indices[i]:indices[i]+len(sources[i])] == sources[i]:
                s = s[0:indices[i]] + targets[i] +                     s[indices[i]+len(sources[i]):]
                print(s)
        return s

题解 3 - rust

• 编辑时间：2023-08-15
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn find_replace_string(
        mut s: String,
        indices: Vec<i32>,
        sources: Vec<String>,
        targets: Vec<String>,
    ) -> String {
        let indices = indices.into_iter().map(|i| i as usize).collect::<Vec<_>>();
        let n = indices.len();
        let mut idxs = (0..n).collect::<Vec<_>>();
        idxs.sort_by_key(|i| indices[*i]);
        idxs.reverse();
        for i in idxs {
            if indices[i] + sources[i].len() <= s.len() && s[indices[i]..indices[i] + sources[i].len()] == sources[i] {
                let mut ns = String::new();
                ns.push_str(&s[0..indices[i]]);
                ns.push_str(&targets[i]);
                ns.push_str(&s[indices[i] + sources[i].len()..]);
                s = ns;
            }
        }
        s
    }
}