本篇為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);
}
public static String reverseString(String s) {
return new StringBuilder(s).reverse().toString();
}
沒有留言:
張貼留言