344.Reverse-String

344. Reverse String

题目地址

https://leetcode.com/problems/reverse-string/

题目描述

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

代码

Approach #1 Recursion, in-Place O(N) Space

class Solution {
  public void reverseString(char[] s) {
    helper(s, 0, s.length - 1)
  }

  private void helper(char[] s, int left, int right) {
        if (left >= right)    return;
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
    helper(s, left, right);
  }

}

Approach 2: Two Pointers, Iteration, O(1) Space

class Solution {
  int left = 0, right = s.length - 1;
  while (left < right) {
    char tmp = s[left];
    s[left++] = s[right];
    s[right--] = tmp;
  }
}