LeetCode 344. Reverse String 字串反轉

本篇為LeetCode上演算法的簡單問題，Reverse String。

題目

Write a function that takes a string as input and returns the string reversed.

Example1:

Input: "hello"
Output: "olleh"

Example2:

Input: "A man, a plan, a canal: Panama"
Output: "amanaP :lanac a ,nalp a ,nam A"

先想到的寫法

把輸入的字串前後翻轉，例如輸入為hello world，輸出為dlrow olleh。

解法如下，將原char陣列最後1個元素放在新char陣列的第1個位置，以此類推。時間複雜度O(n)；空間複雜度O(n)。

public static String reverseString(String s) {
    char[] chars = s.toCharArray();
    int lastIndex = chars.length - 1;
    char[] reverseChars = new char[chars.length];
    for(int i = 0; i < chars.length; i++) {
        reverseChars[i] = chars[lastIndex - i];
    }
    return String.valueOf(reverseChars);
}

更加解

下面的解法速度更快，時間複雜度為O(N/2)；空間複雜度O(1)。前後相對位置的元素兩兩對調，先取出char陣列的第1個元素放在暫存變數，並將最後1個元素放在char陣列的第1個位置，再將暫存變數的值放在char陣列最後1個位置，以此類推，一次迴圈就對調前後兩個元素的位置，所以只要跑陣列長度的1/2次即可。

public static String reverseString(String s) {
    char[] chars = s.toCharArray();
    int lastIndex = chars.length - 1;
    char temp;
    for(int i = 0; i < chars.length/2; i++) {
        temp = chars[i];
        chars[i] = chars[lastIndex - i];
        chars[lastIndex - i] = temp;
    }
    return String.valueOf(chars);
}

或用while迴圈。

public static String reverseString(char[] s) {
    int start = 0;
    int end = s.length - 1;
    while (start < end) {
        char tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
        start++;
        end--;
    }
    return new String(s);
}

或直接用StringBuilder.reverse()。

public static String reverseString(String s) {
    return new StringBuilder(s).reverse().toString();
}

• LeetCode Reverse Words in a String III