編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 char[] 的形式給出。

不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。

你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。

示例 1：

輸入：["h","e","l","l","o"]

輸出：["o","l","l","e","h"]

示例 2：

輸入：["H","a","n","n","a","h"]

輸出：["h","a","n","n","a","H"]

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/reverse-string

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

一、使用棧的FILO進行轉(zhuǎn)換

class Solution {
   public void reverseString(char[] s) {
      Stack<Character> stack = new Stack<>();
      for (char c : s) {
         stack.push(c);
      }
      int i = 0;
      while (!stack.isEmpty()) {
         s[i ++ ] = stack.pop();
      }
   }
}

二、第一個和最后交換，第 i 和 len - 1 - i 交換

class Solution {
   public void reverseString(char[] s) {
      int start = 0;
      int end = s.length - 1;
      while (start < end) {
         char temp = s[end];
         s[end--] = s[start];
         s[start++] = temp;
      }
   }
}

三、第二中方法用遞歸實現(xiàn)

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

   public void reverse(char[] s, int start, int end) {
      if (start > end) {
         return;
      }
      char temp = s[end];
      s[end--] = s[start];
      s[start++] = temp;
      reverse(s, start, end);
   }
}