您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode如何翻转字符串里的单词
## 问题描述
LeetCode第151题"翻转字符串里的单词"要求我们实现一个算法,将给定字符串中的单词顺序进行翻转,同时去除多余的空格。具体要求如下:
- 输入字符串可能包含前导空格、尾随空格和单词间的多个空格
- 返回的字符串应当单词顺序翻转,且单词间用单个空格分隔
- 不能使用任何内置的字符串处理函数(如split、reverse等)
示例:
输入: “ hello world ” 输出: “world hello”
## 解题思路分析
### 方法一:双指针法(最优解)
**核心思想**:先整体翻转字符串,再逐个翻转单词,最后处理空格
1. **去除多余空格**:使用快慢指针法去除字符串中多余的空格
2. **整体翻转**:将整个字符串进行翻转
3. **单词翻转**:识别每个单词的边界,对每个单词进行局部翻转
4. **调整格式**:确保单词间只有一个空格
**时间复杂度**:O(n)
**空间复杂度**:O(1)(对于C++等可修改字符串的语言)
### 方法二:使用栈
**核心思想**:利用栈的先进后出特性实现翻转
1. 遍历字符串,提取单词并压入栈中
2. 依次弹出栈中单词组成新字符串
3. 处理空格问题
**时间复杂度**:O(n)
**空间复杂度**:O(n)
### 方法三:分割+反转(不符合题目要求但实际常用)
虽然题目限制使用内置函数,但在实际开发中可以:
1. 使用split分割单词
2. 反转单词列表
3. 用join连接
## 代码实现(以方法一为例)
### Python实现
```python
def reverseWords(s: str) -> str:
# 去除多余空格
def trim_spaces(s):
left, right = 0, len(s) - 1
# 去掉首尾空格
while left <= right and s[left] == ' ':
left += 1
while left <= right and s[right] == ' ':
right -= 1
# 去掉中间多余空格
output = []
while left <= right:
if s[left] != ' ':
output.append(s[left])
elif output[-1] != ' ':
output.append(s[left])
left += 1
return output
# 反转字符数组
def reverse(l, left, right):
while left < right:
l[left], l[right] = l[right], l[left]
left += 1
right -= 1
# 反转每个单词
def reverse_each_word(l):
n = len(l)
start = end = 0
while start < n:
# 找到单词末尾
while end < n and l[end] != ' ':
end += 1
# 反转单词
reverse(l, start, end - 1)
# 更新指针
start = end + 1
end += 1
# 主流程
l = trim_spaces(s)
reverse(l, 0, len(l) - 1)
reverse_each_word(l)
return ''.join(l)
class Solution {
public String reverseWords(String s) {
// 去除空格
StringBuilder sb = trimSpaces(s);
// 翻转字符串
reverse(sb, 0, sb.length() - 1);
// 翻转每个单词
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder trimSpaces(String s) {
int left = 0, right = s.length() - 1;
while (left <= right && s.charAt(left) == ' ') left++;
while (left <= right && s.charAt(right) == ' ') right--;
StringBuilder sb = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if (c != ' ') {
sb.append(c);
} else if (sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
left++;
}
return sb;
}
public void reverse(StringBuilder sb, int left, int right) {
while (left < right) {
char tmp = sb.charAt(left);
sb.setCharAt(left++, sb.charAt(right));
sb.setCharAt(right--, tmp);
}
}
public void reverseEachWord(StringBuilder sb) {
int n = sb.length();
int start = 0, end = 0;
while (start < n) {
while (end < n && sb.charAt(end) != ' ') end++;
reverse(sb, start, end - 1);
start = end + 1;
end++;
}
}
}
翻转字符串中的单词是一个考察综合字符串处理能力的问题,涉及: 1. 字符串基本操作 2. 双指针技巧 3. 翻转操作实现 4. 边界条件处理
掌握这类问题有助于提升对字符串处理的整体理解,并为更复杂的算法问题打下基础。建议在理解基础解法后,尝试自己实现并考虑各种优化可能性。 “`
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。