LeetCode.344.Reverse String 反转字符串

题目描述

344 Reverse String
https://leetcode-cn.com/problems/reverse-string/
https://leetcode.com/problems/reverse-string/description/

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"]

---

解题过程

新字符串存储

很简单的字符串逆转，没想到竟然没能一次AC。
我第一次用的方法是挨个字符遍历然后倒序累加到新字符串中：

public String reverseString1(String s) {
    String result="";
    for(int i=0; i<s.length(); i++){
        result = s.charAt(i) + result;
    }
    return result;
}

结果最后一个测试用例不通过，超时，如下：
Time Limit Exceeded
475 / 476 test cases passed.

Massorete
Lon
a mallee
Vig
...
Falun
a r... 42490 more chars

是一个4万多字符的超长字符串，然后优化。

原地逆置

改为先转为char数组，然后首尾交换：

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

提交通过了。

前后双指针

别人提交的其他不错的解法
看到一个3ms的，也是转为char数组然后交换，但比我的高端，使用首尾两个指针，代码比较漂亮：

class Solution {
    public String reverseString(String s) {
        char[] c= s.toCharArray();
        int left = 0, right = c.length-1;
        while(left<right)
        {
            char temp = c[left];
            c[left] = c[right];
            c[right] = temp;
            left++;right--;
        }

        return new String(c);
    }
}

看看最快的2ms的代码：

class Solution {
    public String reverseString(String s) {
        char[] charArray = s.toCharArray();
        char[] charArray_2 = new char[charArray.length];
        for (int i = 0; i < charArray.length; i++) {
            charArray_2[charArray_2.length-i-1] = charArray[i];
        }
        return new String(charArray_2);
    }
}

看来用char数组的确是最快的。

Collections.reverse()

还有个43ms的，用java集合操作提供的reverse方法：

public class Solution {
    public String reverseString(String s) {
        List<String> list =  Arrays.asList(s.split(""));
        Collections.reverse(list);

        return String.join("",list);
    }
}

最后还用了String的join方法，是java8中新增的方法，高端！我觉得这个很好啊，有现成的干嘛不用，一开始我也想用来着，只不过没找到reverse()方法在哪个类中，所以还顺便学习了一下java.util.Collections类的用法。

不过后来知道，直接用StringBuffer类或StringBuilder类的reverse()方法即可，所以最简洁的代码如下：

class Solution {
    public String reverseString(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

也只用了4ms而已。

---

GitHub代码

algorithms/leetcode/leetcode/_344_ReverseString.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_344_ReverseString.java

---