算法训练营day09 | {151.翻转字符串里的单词, 卡码网：55.右旋转字符串, 28.实现 strStr()，459.重复的子字符串}

第四章字符串-part02，知识点为字符串反转、双指针。

151.翻转字符串里的单词

题目链接：151.翻转字符串里的单词
文档讲解：代码随想录–151.翻转字符串里的单词
状态：反转字符串还没达到理解并灵活使用的程度；Java语言本身的API不熟练。

1.1 看完题解的想法

Java中String是不可变对象，必须转成char[]数组，但其实用27.移除元素的思想来移除多余的空格，也有两种做法：
1. 遇到第一个空格两个指针正常同时往后移动，连续遇到第二个空格时slow指针不移动。
2. 只保留单词，删除所有空格，遇到非空格、并且slow!=0时，给单词之间手动添加一个空格。
整体思路：
1. 去除前导和后导的空格；
2. 删除多余的空格；
3. 字符串整体反转一次；
4. 字符串按照单词局部再反转一次。

1.2 解题过程

我写的第一版用char[]数组的代码如下，执行效率是最高的：

▶

151.翻转字符串里的单词

public class Solution {
    public String reverseWords(String s) {
        char[] arrS = s.toCharArray();
        char[] res = delExtraSpace(arrS, 0, arrS.length - 1);
        reverse(res, 0, res.length - 1);
        reverseEachWord(res);
        return new String(res);
    }
    
    public void reverseEachWord(char[] arr) {
        int n = arr.length;
        int start = 0, end = 0;
        while(start < n) {
            while (end < n && arr[end] != ' ') end++;  // 找单词末尾
            reverse(arr, start, end - 1);
            start = end + 1;
            end++;
        }
    }

    public void reverse(char[] arr, int left, int right) {
        while(left < right) {
            char tmp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = tmp;
        }
    }

    public char[] delExtraSpace(char[] arr, int start, int end) {
        while(arr[start] == ' ') start++;
        while(arr[end] == ' ') end--;
        int slow = start;
        for (int fast = start; fast <= end; fast++) {
            if(arr[fast] != ' ') arr[slow++] = arr[fast];
            else if (arr[fast - 1] != ' ') arr[slow++] = arr[fast];
        }
        char[] newArr = new char[slow - start];
        System.arraycopy(arr, start, newArr, 0, slow - start);
        return newArr;
    }
}

解法二：调用JAVA语言的API：

▶

调用API版

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> list = Arrays.asList(s.split("\\s+"));
        Collections.reverse(list);
        return String.join(" ", list);
    }
}

解法三：使用StringBuidler来保存字符，执行效率不高：

▶

StringBuilder版

public class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = trimSpaces(s);
        reverse(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return String.valueOf(sb);
    }

    private 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++;
        }
    }

    public StringBuilder trimSpaces(String s) {
        int start = 0, end = s.length() - 1;
        while(s.charAt(start) == ' ') start++;
        while(s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while(start <= end) {
            if (s.charAt(start) != ' ') {
                sb.append(s.charAt(start));
            } else if (s.charAt(start - 1) != ' ') {
                sb.append(' ');
            }
            start++;
        }
        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);
        }
    }
}

解法四：

▶

双端队列

class Solution {
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        int start = 0, end = arr.length - 1;
        while (arr[start] == ' ') start++;
        while (arr[end] == ' ') end--;
        Deque<String> queue = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();
        while(start <= end) {
            if(word.length() != 0 && arr[start] == ' ') {
                queue.offerFirst(word.toString());
                word.setLength(0);
            } else if(arr[start] != ' '){
                word.append(arr[start]);
            }
            start++;
        }
        queue.offerFirst(word.toString());
        return String.join(" ", queue);
    }
}

卡码网：55.右旋转字符串

题目链接：卡码网：55.右旋转字符串
状态：对反转的灵活应用，简单。

2.1 解题过程

反转再局部反转。

▶

卡码网：55.右旋转字符串

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        String str = scanner.next();
        char[] arr = str.toCharArray();

        Main.reverse(arr, 0, arr.length - 1);
        Main.reverse(arr, 0, k - 1);
        Main.reverse(arr, k, arr.length - 1);
        System.out.println(new String(arr));
    }

    public static void reverse(char[] chars, int left, int right) {
        while(left < right) {
            char tmp = chars[left];
            chars[left++] = chars[right];
            chars[right--] = tmp;
        }
    }
}

28. 实现 strStr()

题目链接：28. 实现 strStr()
文档讲解：代码随想录–28. 实现 strStr()
状态：KMP算法，知道是要根据短的串预先算一个数组，然后进行跳转，具体记不清了。

3.1 解题过程

本题用暴力解法O(n^2)通过了，代码如下：

▶

暴力枚举

class Solution {
    public int strStr(String haystack, String needle) {
        char[] longer = haystack.toCharArray();
        char[] local = needle.toCharArray();
        int cnt = 0;
        for (int i = 0; i < longer.length; i++) {
            int k = i;
            for (int j = 0; j < local.length; j++) {
                if (longer[k] == local[j]) {
                    cnt++;
                    k++;
                    if(cnt == local.length) return i;
                    if(k >= longer.length) return -1;
                } else if(cnt < local.length) {
                    cnt = 0;
                    break;
                }
            }
        }
        return -1;
    }
}

459. 重复的子字符串

题目链接：459.重复的子字符串
文档讲解：代码随想录–459.重复的子字符串
视频讲解：字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串
状态：KMP算法，一刷跳过了，容易忘记。

5. JAVA API小结

str.trim(): 去除字符串前导和后导空格；
str.split(regex, limit): 依据正则表达式分割字符串，limit表示应用正则表达式的次数；
Collections.reverse(list): 原地反转一个集合；
System.arrayCopy(strArr, srcPos, desArr, desPos, length): 快速拷贝一个数组。
String.join(CharSequence delimiter, Iterable<? extends CharSequence> elements)：集合中的元素用指定分隔符分隔

6. 字符串小结

双指针法是字符串处理的常客。至今为止，我们在做数组、链表、字符串都用到了双指针法，双指针法并不隶属于某一种数据结构，但能够使用它来提高效率，一般是将O(n^2)时间复杂度，降低为O(n)。有时间还是要把双指针的题目再做一做。

Leetcode > 字符串

#Java #代码随想录

算法训练营day09 | {151.翻转字符串里的单词, 卡码网：55.右旋转字符串, 28.实现 strStr()，459.重复的子字符串}

http://paopaotangzu.xyz/cn/day09_leetcode/

作者

PROTON TANG

发布于

2025年12月26日

许可协议

算法训练营day07 | {344.反转字符串, 541.反转字符串II, 15.三数之和，18.四数之和} 上一篇

算法训练营day10 | {232.用栈实现队列, 225.用队列实现栈, 20.有效的括号，1047.删除字符串中的所有相邻重复项} 下一篇