数据结构和算法【40】翻转字符串

皮皮克克 2023-09-06

点击关注公众号，干货第一时间送达

再来看一道经典的字符串问题，

翻转字符串。

一、屏幕前的吴彦祖和刘亦菲们，请听题

举个例子：

题目要求的是额外空间复杂度是O(1)

咋整呢？

二、解题

（1）可以先整体逆序字符数组

str = "i love dog very much" 整体逆序为：

str` = "hcum yrev god evol i"

（2）然后再把每个单词逆序即可，单词之间可以通过空格分割

str` 每个单词逆序，

转换为：str`` = "much very dog love i"

具体操作，看看代码。

完整代码：

public class CodingDemo {

    /**
     * TODO: 翻转字符串
     * @param
     */
    private static void rotateWord(char[] ch){
        if (ch == null || ch.length == 0){
            return;
        }

        //1，先整体逆序
        reverse(ch, 0, ch.length-1);

        //2, 然后遍历，每遇到一个单词，把单词逆序
        int l = -1;
        int r = -1;
        for (int i = 0; i < ch.length; i++) {
            //找到每个单词之间空格分割
            if (ch[i] != ' '){
                l = i == 0 || ch[i-1] == ' ' ? i : l;
                r = i == ch.length-1 || ch[i+1] == ' ' ? i : r;
            }

            //逆序每个单词
            if (l != -1 && r != -1){
                reverse(ch, l, r);
                l = -1;
                r = -1;
            }
        }
    }

    /**
     * 逆序 start ~ end 范围内字符
     * @param ch
     * @param start
     * @param end
     */
    private static void reverse(char[] ch, int start, int end){
        while (start < end){
            char tmp = ch[start];
            ch[start] = ch[end];
            ch[end] = tmp;
            start++;
            end--;
        }
    }


    public static void main(String[] args) {

        String str = "i love dog very much";
        char[] chars = str.toCharArray();
        rotateWord(chars);
        System.out.println(String.valueOf(chars));
    }
}

输出：

D:\java\bin\java.exe
much very dog love i

结束语：

Ok，到此为止，就是本篇文章的全部内容了。

该文章主要讲了数据结构和算法: 翻转字符串。

如果各位有不懂的地方，欢迎发消息给小编，小编会进行详细地解答。

最后，请屏幕前的各位吴彦祖和刘亦菲们，动动你们的小手，给小编一个

单词

文章转载自皮皮克克，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构和算法【40】翻转字符串

评论