網頁

2018/12/11

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();
}


沒有留言:

張貼留言