LeetCode-344-反转字符串

请编写一个函数，其功能是将输入的字符串反转过来。

示例：

输入："hello"
输出："olleh"

---

分析：

题目意思很简单，很容易理解。就是把字符串给倒序输出，并且不使用系统提供的API。

下面使用多种解法解答：

解法一：

把String转换成char字符数组，然后倒序遍历这个数组，把结果存入StringBuilder里面。

    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        StringBuilder builder = new StringBuilder();
        char[] chars = s.toCharArray();
        for (int i = chars.length - 1; i >= 0; i--) {
            builder.append(chars[i]);
        }
        return builder.toString();
    }

解法二：

新建一个char类型的数组，倒序存放用来存放String的每一个字符。

    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        int length = s.length();
        char[] array = new char[length];
        for (int i = 0; i < length; i++) {
            array[i] = s.charAt(length - 1 - i);
        }
        return new String(array);
    }

实际上还有优化解法，遍历只需要执行字符串长度的一半即可。

public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        char[] chars = s.toCharArray();
        int length = chars.length;
        char temp;
        for (int i = 0; i < length / 2; i++) {
            temp = chars[i];
            chars[i] = chars[length - 1 - i];
            chars[length - 1 - i] = temp;
        }
        return new String(chars);
    }

解法三：

使用栈，后进先出的特点正好用于反转字符串。把字符串转换为char数组，创建Stack对象，把char数组压入栈，在依次弹出。

    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        char[] chars = s.toCharArray();

        Stack<Character> stack = new Stack<>();
        for (char c : chars) {
            stack.push(c);
        }

        for (int i = 0; i < chars.length; i++) {
            chars[i] = stack.pop();
        }
        return new String(chars);
    }

解法四：

利用异或交换位置的方法，char类型的字符本质上是整数。

char：  H  e   l   l   o
ASCII: 72 101 108 108 111

利用异或交换公式：

a = a ^ b;
b = a ^ b;
a = a ^ b;

代码如下：

    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        char[] chars = s.toCharArray();
        int value = s.length() - 1;
        for (int i = 0; i < value; i++, value--) {
            chars[i] ^= chars[value];
            chars[value] ^= chars[i];
            chars[i] ^= chars[value];

        }
        return new String(chars);
    }

解法五：

反转字符串可以理解为，第一个字符和剩下所有的字符串交换位置，交换完之后，剩下的字符串又可以理解为第一个字符和再剩下的所有字符串交换。

"abcdef" --> "bcdef" "a"
"bcdefa" --> "cdef" "b" "a"
"cdefba" --> "def" "c" "ba"
"defcba" --> "ef" "d" "cba"
"efdcba" --> "f" "e" "dcba"
"fedcba"

最终，fedcba就是需要的结果。
所以我们可以使用递归的方法，递归执行，直到剩下的字符传长度为1。但这种方法仅提供一种解题思路，因为效率比较低，超出了平台的时间限制。

    public String reverseString(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }

        String result = recursionFindString(s);
        return result;
    }
    
    private String recursionFindString(String s){
        if(s.length() == 1){
            return s;
        }else{
            return recursionFindString(s.substring(1)) + s.charAt(0);
        }
    }

参考链接：https://www.cnblogs.com/JohnTsai/p/5606719.html