字符串反转

环境：windows7 sp1，eclipse，jdk1.6

这里提供三种方法实现。

（1）使用循环而非递归，时间复杂度O(n)，空间复杂度T(n）。

public String reverseLoop(String s){ if(s == null || s.length() <= 1){ return s; } StringBuffer sb = new StringBuffer(); int l = s.length(); for(int i = l - 1 ; i >= 0 ; i--){ sb.append(s.charAt(i)); } return sb.toString(); } （2）使用递归，时间复杂度好像是n的立方，空间复杂度n的平方。

public String reverseRecursive1(String s){ if(s == null || s.length() <= 1){ return s; } return reverseRecursive1(s.substring(1)) + s.charAt(0); } public String reverseRecursive2(String s){ if(s == null || s.length() <= 1){ return s; } int l = s.length(); return s.charAt(l - 1) + reverseRecursive2(s.substring(0, l - 1)); }

使用递归时，给出了两个细节稍微有所不同的方法。reverseRecursive1()方法是在递归时把每个字符串的第一个字符放在末尾，从后向前生成反转后的字符串。reverseRecursive2()方法是在递归时把每个字符串的最后一个字符放在前端，从前往后生成反转后的字符串。

（3）使用StringBuffer方法

public String StringReverseMethod(String s){ if(s == null || s.length() <= 1){ return s; } StringBuffer sb = new StringBuffer(s); return sb.reverse().toString(); }

遗留问题：时间复杂度和空间复杂度

引申问题：字符串反转可以实现的字符串的最大数量是多少？