LeetCode每日一题(2109. Adding Spaces to a String)

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

For example, given s = “EnjoyYourCoffee” and spaces = [5, 9], we place spaces before ‘Y’ and ‘C’, which are at indices 5 and 9 respectively. Thus, we obtain “Enjoy Your Coffee”.
Return the modified string after the spaces have been added.

Example 1:

Input: s = “LeetcodeHelpsMeLearn”, spaces = [8,13,15]
Output: “Leetcode Helps Me Learn”

Explanation:
The indices 8, 13, and 15 correspond to the underlined characters in “LeetcodeHelpsMeLearn”.
We then place spaces before those characters.

Example 2:

Input: s = “icodeinpython”, spaces = [1,5,7,9]
Output: “i code in py thon”

Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in “icodeinpython”.
We then place spaces before those characters.

Example 3:

Input: s = “spacing”, spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"

Explanation:
We are also able to place spaces before the first character of the string.

Constraints:

• 1 <= s.length <= 3 * 105
• s consists only of lowercase and uppercase English letters.
• 1 <= spaces.length <= 3 * 105
• 0 <= spaces[i] <= s.length - 1
• All the values of spaces are strictly increasing.

---

假设当前要插入的 index 为 i， 当前已经在原字符串中插入了 n 个空格了, 那实际要插入的 index 就变成了 i + n
但是 rust 用这个方法完成整体耗时一秒多，可能与 String 底层的实现有关，一旦超过当前字符串所分配的容量，那一次插入就要重新分配一次内存, 不过不知道这种重分配会多频繁， 应该不至于每次插入都重新分配吧。改天用 split 然后再拼接的方法做一次，看看速度会不会快一点

---

impl Solution {
    
    pub fn add_spaces(mut s: String, spaces: Vec<i32>) -> String {
    
        let mut added = 0;
        for si in spaces {
    
            s.insert(si as usize + added, ' ');
            added += 1;
        }
        s
    }
}