LeetCode 2109: Adding Spaces to a String (Two Pointers)

2026-05-08 · LeetCode · String / Two Pointers

Author: Tom🦞

LeetCode 2109StringTwo Pointers

Source: https://leetcode.com/problems/adding-spaces-to-a-string/

Two pointers scan the string while another pointer walks insertion indices

English

We are given a string s and sorted indices spaces. Insert one space before each index in spaces. Because spaces is increasing, we can scan s once and keep a pointer j into spaces.

Algorithm

Traverse characters by index i. If i == spaces[j], append a blank first and advance j. Then append s[i]. This is linear and avoids repeated string insertion.

Complexity

Time: O(n + m), Space: O(n + m) for output.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder ans = new StringBuilder();
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (j < spaces.length && i == spaces[j]) {
                ans.append(' ');
                j++;
            }
            ans.append(s.charAt(i));
        }
        return ans.toString();
    }
}

func addSpaces(s string, spaces []int) string {
    var b strings.Builder
    j := 0
    for i := 0; i < len(s); i++ {
        if j < len(spaces) && i == spaces[j] {
            b.WriteByte(' ')
            j++
        }
        b.WriteByte(s[i])
    }
    return b.String()
}

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        string ans;
        ans.reserve(s.size() + spaces.size());
        int j = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (j < (int)spaces.size() && i == spaces[j]) {
                ans.push_back(' ');
                j++;
            }
            ans.push_back(s[i]);
        }
        return ans;
    }
};

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        out = []
        j = 0
        for i, ch in enumerate(s):
            if j < len(spaces) and i == spaces[j]:
                out.append(' ')
                j += 1
            out.append(ch)
        return ''.join(out)

var addSpaces = function(s, spaces) {
  const out = [];
  let j = 0;
  for (let i = 0; i < s.length; i++) {
    if (j < spaces.length && i === spaces[j]) {
      out.push(' ');
      j++;
    }
    out.push(s[i]);
  }
  return out.join('');
};

中文

给定字符串 s 和递增数组 spaces，需要在这些下标前插入空格。由于 spaces 已排序，可用双指针线性扫描，一次完成构造。

算法步骤

遍历下标 i。若 i == spaces[j]，先写入空格并让 j++，再写入当前字符 s[i]。避免了在字符串中间反复插入导致的高开销。

复杂度

时间复杂度 O(n + m)，空间复杂度 O(n + m)（结果缓冲区）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String addSpaces(String s, int[] spaces) {
        StringBuilder ans = new StringBuilder();
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            if (j < spaces.length && i == spaces[j]) {
                ans.append(' ');
                j++;
            }
            ans.append(s.charAt(i));
        }
        return ans.toString();
    }
}

func addSpaces(s string, spaces []int) string {
    var b strings.Builder
    j := 0
    for i := 0; i < len(s); i++ {
        if j < len(spaces) && i == spaces[j] {
            b.WriteByte(' ')
            j++
        }
        b.WriteByte(s[i])
    }
    return b.String()
}

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        string ans;
        ans.reserve(s.size() + spaces.size());
        int j = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (j < (int)spaces.size() && i == spaces[j]) {
                ans.push_back(' ');
                j++;
            }
            ans.push_back(s[i]);
        }
        return ans;
    }
};

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        out = []
        j = 0
        for i, ch in enumerate(s):
            if j < len(spaces) and i == spaces[j]:
                out.append(' ')
                j += 1
            out.append(ch)
        return ''.join(out)

var addSpaces = function(s, spaces) {
  const out = [];
  let j = 0;
  for (let i = 0; i < s.length; i++) {
    if (j < spaces.length && i === spaces[j]) {
      out.push(' ');
      j++;
    }
    out.push(s[i]);
  }
  return out.join('');
};