LeetCode 557: Reverse Words in a String III (In-Word Two-Pointer Reversal)
LeetCode 557StringTwo PointersSimulationToday we solve LeetCode 557 - Reverse Words in a String III.
Source: https://leetcode.com/problems/reverse-words-in-a-string-iii/
English
Problem Summary
Given a string s, reverse characters in each word while keeping the original word order and preserving single spaces between words.
Key Insight
Word boundaries are separated by spaces. We can scan the string and reverse every continuous non-space segment independently.
Algorithm
1) Convert s to a mutable char array.
2) Use pointer i to find a word start, then move j to word end.
3) Reverse range [i, j-1] in-place with two pointers.
4) Continue from j+1 until finish.
Complexity Analysis
Time: O(n).
Space: O(n) if language strings are immutable (or O(1) extra on mutable char arrays).
Common Pitfalls
- Reversing entire sentence instead of per word.
- Off-by-one when reversing [i, j-1].
- Forgetting to skip spaces before next word.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String reverseWords(String s) {
char[] a = s.toCharArray();
int n = a.length;
int i = 0;
while (i < n) {
while (i < n && a[i] == ' ') i++;
int j = i;
while (j < n && a[j] != ' ') j++;
reverse(a, i, j - 1);
i = j + 1;
}
return new String(a);
}
private void reverse(char[] a, int l, int r) {
while (l < r) {
char t = a[l];
a[l] = a[r];
a[r] = t;
l++;
r--;
}
}
}func reverseWords(s string) string {
a := []byte(s)
n := len(a)
reverse := func(l, r int) {
for l < r {
a[l], a[r] = a[r], a[l]
l++
r--
}
}
i := 0
for i < n {
for i < n && a[i] == ' ' {
i++
}
j := i
for j < n && a[j] != ' ' {
j++
}
reverse(i, j-1)
i = j + 1
}
return string(a)
}class Solution {
public:
string reverseWords(string s) {
int n = (int)s.size();
int i = 0;
while (i < n) {
while (i < n && s[i] == ' ') i++;
int j = i;
while (j < n && s[j] != ' ') j++;
reverse(s.begin() + i, s.begin() + j);
i = j + 1;
}
return s;
}
};class Solution:
def reverseWords(self, s: str) -> str:
arr = list(s)
n = len(arr)
i = 0
def rev(l: int, r: int) -> None:
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
while i < n:
while i < n and arr[i] == ' ':
i += 1
j = i
while j < n and arr[j] != ' ':
j += 1
rev(i, j - 1)
i = j + 1
return ''.join(arr)var reverseWords = function(s) {
const a = s.split('');
const n = a.length;
function rev(l, r) {
while (l < r) {
const t = a[l];
a[l] = a[r];
a[r] = t;
l++;
r--;
}
}
let i = 0;
while (i < n) {
while (i < n && a[i] === ' ') i++;
let j = i;
while (j < n && a[j] !== ' ') j++;
rev(i, j - 1);
i = j + 1;
}
return a.join('');
};中文
题目概述
给定字符串 s，把每个单词内部字符反转，但单词顺序不变，空格位置规则保持不变。
核心思路
空格天然把字符串分割成一个个单词。逐段定位每个单词区间，然后在该区间内做双指针反转即可。
算法步骤
1）把字符串转为可修改字符数组。
2）指针 i 找到单词开头，j 找到单词结尾后一个位置。
3）反转区间 [i, j-1]。
4）继续处理下一个单词，直到结束。
复杂度分析
时间复杂度：O(n)。
空间复杂度：在字符串不可变语言中为 O(n)；若原地可改则额外空间可视为 O(1)。
常见陷阱
- 把整句整体反转了，而不是逐词反转。
- 反转边界写错，导致遗漏首尾字符。
- 忘记先跳过空格，导致区间定位错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String reverseWords(String s) {
char[] a = s.toCharArray();
int n = a.length;
int i = 0;
while (i < n) {
while (i < n && a[i] == ' ') i++;
int j = i;
while (j < n && a[j] != ' ') j++;
reverse(a, i, j - 1);
i = j + 1;
}
return new String(a);
}
private void reverse(char[] a, int l, int r) {
while (l < r) {
char t = a[l];
a[l] = a[r];
a[r] = t;
l++;
r--;
}
}
}func reverseWords(s string) string {
a := []byte(s)
n := len(a)
reverse := func(l, r int) {
for l < r {
a[l], a[r] = a[r], a[l]
l++
r--
}
}
i := 0
for i < n {
for i < n && a[i] == ' ' {
i++
}
j := i
for j < n && a[j] != ' ' {
j++
}
reverse(i, j-1)
i = j + 1
}
return string(a)
}class Solution {
public:
string reverseWords(string s) {
int n = (int)s.size();
int i = 0;
while (i < n) {
while (i < n && s[i] == ' ') i++;
int j = i;
while (j < n && s[j] != ' ') j++;
reverse(s.begin() + i, s.begin() + j);
i = j + 1;
}
return s;
}
};class Solution:
def reverseWords(self, s: str) -> str:
arr = list(s)
n = len(arr)
i = 0
def rev(l: int, r: int) -> None:
while l < r:
arr[l], arr[r] = arr[r], arr[l]
l += 1
r -= 1
while i < n:
while i < n and arr[i] == ' ':
i += 1
j = i
while j < n and arr[j] != ' ':
j += 1
rev(i, j - 1)
i = j + 1
return ''.join(arr)var reverseWords = function(s) {
const a = s.split('');
const n = a.length;
function rev(l, r) {
while (l < r) {
const t = a[l];
a[l] = a[r];
a[r] = t;
l++;
r--;
}
}
let i = 0;
while (i < n) {
while (i < n && a[i] === ' ') i++;
let j = i;
while (j < n && a[j] !== ' ') j++;
rev(i, j - 1);
i = j + 1;
}
return a.join('');
};
Comments