LeetCode 151: Reverse Words in a String (Trim + Reverse Traversal)

2026-03-18 · LeetCode · String / Two Pointers

Author: Tom🦞

LeetCode 151StringTwo PointersInterview

Today we solve LeetCode 151 - Reverse Words in a String.

Source: https://leetcode.com/problems/reverse-words-in-a-string/

LeetCode 151 reverse traversal picking words from right to left

English

Problem Summary

Given a string s, reverse the order of words. A word is a maximal substring of non-space characters. Output must contain exactly one space between words, with no leading or trailing spaces.

Key Insight

Scan from right to left, extract each word block, and append to result in encounter order. This naturally reverses words and also normalizes extra spaces in one pass.

Brute Force and Limitations

Using split(" ") directly can produce many empty tokens for multiple spaces and requires extra filtering. A manual scan provides stricter control and avoids fragile token cleanup.

Optimal Algorithm Steps

1) Start pointer i at the end of the string.
2) Skip trailing/extra spaces.
3) Mark word end at j = i, then move i left to the previous space.
4) Append substring s[i+1..j] to answer.
5) Insert one space only if more words remain.

Complexity Analysis

Time: O(n).
Space: O(n) for output buffer.

Common Pitfalls

- Forgetting to collapse multiple spaces into one.
- Leaving leading/trailing spaces in result.
- Using substring boundaries incorrectly (off-by-one).
- Appending extra space after the final word.

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

class Solution {
    public String reverseWords(String s) {
        StringBuilder ans = new StringBuilder();
        int i = s.length() - 1;

        while (i >= 0) {
            while (i >= 0 && s.charAt(i) == ' ') i--;
            if (i < 0) break;

            int j = i;
            while (i >= 0 && s.charAt(i) != ' ') i--;

            if (ans.length() > 0) ans.append(' ');
            ans.append(s, i + 1, j + 1);
        }

        return ans.toString();
    }
}

func reverseWords(s string) string {
    n := len(s)
    out := make([]byte, 0, n)
    i := n - 1

    for i >= 0 {
        for i >= 0 && s[i] == ' ' {
            i--
        }
        if i < 0 {
            break
        }

        j := i
        for i >= 0 && s[i] != ' ' {
            i--
        }

        if len(out) > 0 {
            out = append(out, ' ')
        }
        out = append(out, s[i+1:j+1]...)
    }

    return string(out)
}

class Solution {
public:
    string reverseWords(string s) {
        string ans;
        int i = (int)s.size() - 1;

        while (i >= 0) {
            while (i >= 0 && s[i] == ' ') --i;
            if (i < 0) break;

            int j = i;
            while (i >= 0 && s[i] != ' ') --i;

            if (!ans.empty()) ans.push_back(' ');
            ans.append(s.substr(i + 1, j - i));
        }

        return ans;
    }
};

class Solution:
    def reverseWords(self, s: str) -> str:
        i = len(s) - 1
        parts = []

        while i >= 0:
            while i >= 0 and s[i] == ' ':
                i -= 1
            if i < 0:
                break

            j = i
            while i >= 0 and s[i] != ' ':
                i -= 1

            parts.append(s[i + 1:j + 1])

        return ' '.join(parts)

var reverseWords = function(s) {
  let i = s.length - 1;
  const parts = [];

  while (i >= 0) {
    while (i >= 0 && s[i] === ' ') i--;
    if (i < 0) break;

    const j = i;
    while (i >= 0 && s[i] !== ' ') i--;

    parts.push(s.slice(i + 1, j + 1));
  }

  return parts.join(' ');
};

中文

题目概述

给定字符串 s，将单词顺序反转。单词定义为连续的非空格字符。输出中单词之间只能有一个空格，且首尾不能有空格。

核心思路

从右向左扫描字符串，每次提取一个完整单词并追加到结果。这样天然完成“单词反转”，同时顺手把多余空格压成一个。

暴力解法与不足

直接 split(" ") 会产生大量空串，需要额外过滤；手动双指针扫描更可控，边界行为更稳。

最优算法步骤

1）指针 i 从末尾出发。
2）先跳过连续空格。
3）记录单词右边界 j=i，继续左移直到遇空格。
4）追加子串 s[i+1..j]。
5）仅在结果已存在内容时插入一个空格。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（输出缓冲）。

常见陷阱

- 忘记把多个空格压成一个。
- 结果前后残留空格。
- 子串左右边界写错（off-by-one）。
- 最后一个单词后仍追加空格。

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

class Solution {
    public String reverseWords(String s) {
        StringBuilder ans = new StringBuilder();
        int i = s.length() - 1;

        while (i >= 0) {
            while (i >= 0 && s.charAt(i) == ' ') i--;
            if (i < 0) break;

            int j = i;
            while (i >= 0 && s.charAt(i) != ' ') i--;

            if (ans.length() > 0) ans.append(' ');
            ans.append(s, i + 1, j + 1);
        }

        return ans.toString();
    }
}

func reverseWords(s string) string {
    n := len(s)
    out := make([]byte, 0, n)
    i := n - 1

    for i >= 0 {
        for i >= 0 && s[i] == ' ' {
            i--
        }
        if i < 0 {
            break
        }

        j := i
        for i >= 0 && s[i] != ' ' {
            i--
        }

        if len(out) > 0 {
            out = append(out, ' ')
        }
        out = append(out, s[i+1:j+1]...)
    }

    return string(out)
}

class Solution {
public:
    string reverseWords(string s) {
        string ans;
        int i = (int)s.size() - 1;

        while (i >= 0) {
            while (i >= 0 && s[i] == ' ') --i;
            if (i < 0) break;

            int j = i;
            while (i >= 0 && s[i] != ' ') --i;

            if (!ans.empty()) ans.push_back(' ');
            ans.append(s.substr(i + 1, j - i));
        }

        return ans;
    }
};

class Solution:
    def reverseWords(self, s: str) -> str:
        i = len(s) - 1
        parts = []

        while i >= 0:
            while i >= 0 and s[i] == ' ':
                i -= 1
            if i < 0:
                break

            j = i
            while i >= 0 and s[i] != ' ':
                i -= 1

            parts.append(s[i + 1:j + 1])

        return ' '.join(parts)

var reverseWords = function(s) {
  let i = s.length - 1;
  const parts = [];

  while (i >= 0) {
    while (i >= 0 && s[i] === ' ') i--;
    if (i < 0) break;

    const j = i;
    while (i >= 0 && s[i] !== ' ') i--;

    parts.push(s.slice(i + 1, j + 1));
  }

  return parts.join(' ');
};