344. Reverse String【easy】
Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".
解法一：
class Solution {
public:
string reverseString(string s) {
int start = , end = s.length() - ;
while (start <= end) {
char c = s[start];
s[start] = s[end];
s[end] = c;
++start;
--end;
}
return s;
}
};
解法二：
class Solution {
public:
void reverseStringHelper(string & s, int len, int start, string & result)
{
if (start == len) {
return;
}
reverseStringHelper(s, len, start + , result);
result += s[start];
}
string reverseString(string s) {
string result;
reverseStringHelper(s, s.length(), , result);
return result;
}
};
递归
解法三：
public class Solution {
public String reverseString(String s) {
int length = s.length();
if (length <= ) return s;
String leftStr = s.substring(, length / );
String rightStr = s.substring(length / , length);
return reverseString(rightStr) + reverseString(leftStr);
}
}
参考@ratchapong.t 的代码
Complexity Analysis
Time Complexity: `O(n log(n))` (Average Case) and `O(n * log(n))` (Worst Case) where `n` is the total number character in the input string. The recurrence equation is `T(n) = 2 * T(n/2) + O(n)`. `O(n)` is due to the fact that concatenation function takes linear time. The recurrence equation can be solved to get `O(n * log(n))`.
Auxiliary Space: `O(h)` space is used where `h` is the depth of recursion tree generated which is `log(n)`. Space is needed for activation stack during recursion calls.
Algorithm
Approach: Divide and Conquer (Recursive)
The string is split into half. Each substring will be further divided. This process continues until the string can no longer be divided (length `<= 1`). The conquering process will take they previously split strings and concatenate them in reverse order.