Write a function to reverse a string

[GingerBear]

注：好久没做题的，热个身吧 来源：The Five Essential Phone-Screen Questions

[GingerBear]

static String reverseString(String str) {
    String ret = "";
    int len = str.length();
    for (int i = 0; i < len; i++) {
        ret += str.charAt(len - i - 1);
    }
    return ret;
}

// test
public static void main(String [] args) {
    sampleAssert(reverseString("abc").equals("cba"), "abc");
    sampleAssert(reverseString("").equals(""), "blank");
    sampleAssert(reverseString("sdf we ").equals(" ew fds"), "with blank");
}

// test helper
static void sampleAssert(Boolean ifSuccess, String msg){

    if (ifSuccess) {
        System.out.println("SUCCESS:\t" + msg);
    }else{
        System.out.println("FAILS:\t" + msg);
    }
}

时间复杂度O(n) // 因为循环次数随字符串长度线性增加 空间复杂度O(1) // 不确定，待解答

一个讨论

据说String在Java里直接append字符串会重新在背后new一个string，也就是

ret += str.charAt(len - i - 1);

会比较慢，所以这个时间复杂度可能不是简单地O(n)，用string buffer就会比较快，待优化算法，待深入研究。@gj835 @liyangbin 求一个优化方案。

[dianadujing]

public class Reverse {
    public static String reverse(String s){
        char[] charArray=s.toCharArray();
        int length=charArray.length;
        char[] newArray = new char[length];

        for(int i=0;i<length;i++){
            newArray[length-i-1]=charArray[i];
        }
        String newString = new String(newArray);
        return newString;
    }
    public static void main(String[] args){
        String s="abcdefg";
        System.out.println("before reversion:"+s);
        System.out.println("after reversion:"+reverse(s));
    }    
}

Time complexity: O(n)

[GingerBear]

@dianadujing 你的方法比较好，表面上看起来差不多，但其实效率差好多，测试了一下：

char[] strArray = new char[100000];
for (int i = 0; i < 100000; i++) {
    strArray[i] = 'a';
}
String str = new String(strArray);

long startTime = System.currentTimeMillis();
reverseString(str);
long finishTime = System.currentTimeMillis();
System.out.println("reverseString took: "+(finishTime-startTime)+ " ms");

startTime = System.currentTimeMillis();
reverseDJ(str);
finishTime = System.currentTimeMillis();
System.out.println("reverseDJ took: "+(finishTime-startTime)+ " ms");

结果：

reverseString took: 9118 ms
reverseDJ took: 4 ms

调查结果是：

a += b

等于

a = new StringBuilder()
    .append(a)
    .append(b)
    .toString();

所以每+=一次就new了一次。

[dianadujing]

@GingerBear 你的探索精神值得鼓励！

[ZoeInSea]

String 确实每次“+=”的过程是new String的过程，可以用StringBuilder代替String，效率快很多，每次append就可以了

[GingerBear]

@yuxiye 恩，是的，不过还是 @dianadujing 的方法快一点点（抱歉开始钻牛角尖），测了一下啊StringBuilder大概8ms的样子。

[ZoeInSea]

public class StringReverse{

  public static String reverse(String str){
    char[] charArray = str.toCharArray();
    int len = charArray.length;
    for(int i = 0; i<len/2; i++){
      char temp = charArray[i];
      charArray[i] = charArray[len-i-1];
      charArray[len-i-1]= temp; 
    }    
    return new String(charArray);
  }

  public static void main(String[] args){
    String str = "abc def  g;";
    String newStr = reverse(str);
    System.out.println(newStr);
  }
}

[hyhuang1218]

Code:

public class ReverseString{

public static String reverse(String s){
    StringBuffer sb = new StringBuffer();       
    for(int i=s.length() -1; i>=0; i--){
        sb.append(s.charAt(i));                     
    }
    return sb.toString();   
}

public static void main(String[] args){
    long startTime = System.currentTimeMillis();
    System.out.println(reverse("abcdefghijklmn"));
    long endTime = System.currentTimeMillis();
    System.out.println(endTime-startTime);

}

}

输出:

nmlkjihgfedcba 0

[GingerBear]

@hyhuang1218 欢迎加入！

[yuweizhan]

public class ReverseString {
  static String reverse(String str) {
    StringBuffer newStr = new StringBuffer();

    for (int i = str.length() - 1; i >= 0; i--)
      newStr.append(str.charAt(i));

    return newStr.toString();
  }

  public static void main(String[] args) {
    System.out.println(reverse("hello world!"));
  }
}

不知道有没有人有同样的问题，我经常会把Arrays和StringBuffer转换成String的方法混起来，两者用法是不同的：

java.util.Arrays.toString(anArray);

aStringBuffer.toString();

[zhangyichi12]

//
//  inverseStr.cpp
//  inverse_Str
//
//  Created by Yichi_Zhang on 2/3/14.
//  Copyright (c) 2014 YichiZhang. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[])
{

    std::string s;
    unsigned long len;
    const char *cp = 0;
    std::cin >> s;
    len = s.length();
    cp = s.c_str();
    while(len != -1){
        std::cout << *(cp+len);
        len = len - 1;
    }   
    return 0;
}