什么是在Java中以递归方式反转字符串的最佳方法？
我今天一直在搞乱递归。 通常编程技术不够用。
我开始以递归方式反转一个字符串。 这就是我想出的：
//A method to reverse a string using recursion public String reverseString(String s){ char c = s.charAt(s.length()-1); if(s.length() == 1) return Character.toString(c); return c + reverseString(s.substring(0,s.length()-1)); } 我的问题：Java中有更好的方法吗？
最好的方法是不使用递归。 这些东西通常用于教学生递归概念，而不是实际的最佳实践。 所以你这样做的方式很好。 只是不要在Java中使用递归在现实世界的应用程序中的这些东西;）
PS。 除了我刚才所说的，我选择""作为递归函数的基本情况：
public String reverseString(String s){ if (s.length() == 0) return s; return reverseString(s.substring(1)) + s.charAt(0); }
如果要执行此操作，则需要对字符数组进行操作，因为String是不可变的，如果以这种方式执行，您将会在整个地方复制字符串。
这是未经测试的，完全是意识流。 它可能在某个地方有一个OB1。 而且非常不是Java。
public String reverseString(String s) { char[] cstr = s.getChars(); reverseCStr(cstr, 0, s.length - 1); return new String(cstr); } /** * Reverse a character array in place. */ private void reverseCStr(char[] a, int s, int e) { // This is the middle of the array; we're done. if (e - s <= 0) return; char t = a[s]; a[s] = a[e]; a[e] = t; reverseCStr(a, s + 1, e - 1); }
你不想深深地筑巢。 分而治之是必须走的路。 还减少了临时字符串的总大小，并且可以并行化。
public static String reverseString(String str) { int len = str.length(); return len<=1 ? str : ( reverseString(str.substring(len/2))+ reverseString(str.substring(0, len/2)) ); }
（未测试 - 这是stackoverflow。）
String.concat而不是+会以牺牲清晰度为代价来提高性能。
编辑：只是为了好玩，一个天真算法的尾递归友好版本。
public static String reverseString(String str) { return reverseString("", str); } private static String reverseString(String reversed, String forward) { return forward.equals("") ? reversed : ( reverseString(reversed+forward.charAt(0), forward.substring(1)) ); }
代理对的正确处理留给感兴趣的读者。
这是我的递归反向函数，工作正常
public static String rev(String instr){ if(instr.length()<=1){ return instr; } else { return (instr.charAt(instr.length()-1)+rev(instr.substring(0,instr.length()-1)) ); } }
只是为了它，它是一个使用StringBuilder的尾递归方法（通常推荐使用String的方法）。
public String reverseString(String s_) { StringBuilder r = new StringBuilder(); StringBuilder s = new StringBuilder(s_); r = reverseStringHelper(r, s); return r.toString(); } private StringBuilder reverseStringHelper(StringBuilder r, StringBuilder s) { if (s.length() == 0) return r; else return reverseStringHelper(r.append(s.charAt(0)), s.deleteCharAt(0)); }
未经测试，我多年没有处理过Java，但这应该是正确的。
如果您正在编写实际代码（不学习递归），请使用StringBuilder的reverse（）方法。 Java Tutorial提供了这个示例：
String palindrome = "Dot saw I was Tod"; StringBuilder sb = new StringBuilder(palindrome); sb.reverse(); // reverse it System.out.println(sb);
这取决于你定义的“更好”。 :-)严肃地说，但是; 您的解决方案基本上使用最大递归深度; 如果堆栈大小是你对“更好”的定义所关注的，那么你最好使用这样的东西：
public String reverseString(String s) { if (s.length() == 1) return s; return reverseString(s.substring(s.length() / 2, s.length() -1) + reverseString(0, s.length() / 2); }
这是我发现工作和使用递归。 您可以将str.length()作为strLength参数传递
private static String reverse(String str, int strLength) { String result = ""; if(strLength > 0) result = str.charAt(strLength - 1) + reverse(str, strLength - 1); return result; }
在Java中，由于String是不可变的，因此String连接将比它看起来更复杂。
对于每个连接，它创建一个复制原始String的内容的新字符串，导致线性复杂度O（n） ，其中n是字符串的长度，因此对于m这样的操作，它是O（m * n） ，我们可以说它具有二次复杂度O（n ^ 2） 。
我们可以使用StringBuilder，每个附加都有O（1）复杂度。 下面是使用StringBuilder的递归程序。 这只使用n / 2个堆栈帧，因此它比正常的递归调用具有更小的空间复杂度，就像s.charAt(s.length-1) + reverse(s.subString(0, s.length-2);
public class StringReverseRecursive { public static void main(String[] args) { String s = "lasrever gnirts fo noitatnemelpmi evisrucer a si sihT"; StringBuilder sb = new StringBuilder(s); reverse(s, sb, 0, sb.length() - 1); System.out.println(sb.toString()); } public static void reverse(String s, StringBuilder sb, int low, int high) { if (low > high) return; sb.setCharAt(low, s.charAt(high)); sb.setCharAt(high, s.charAt(low)); reverse(s, sb, ++low, --high); } }
这绝对是我如何以递归方式反转一个字符串（尽管在你的条件下将它扩展到一个空字符串的情况可能会很好。）我认为没有任何根本更好的方法。
编辑：如果你得到我的漂移，而不是制作子串，在字符数组上操作并在递归链上传递“截止”长度可能更有效。 然而，这并不值得挑剔，因为它首先不是一种非常有效的技术。
您捕获了基本想法，但提取最后一个字符并不能提高清晰度。 我更喜欢以下，其他人可能不喜欢：
public class Foo { public static void main(String[] argv) throws Exception { System.out.println(reverse("a")); System.out.println(reverse("ab")); System.out.println(reverse("abc")); } public final static String reverse(String s) { // oft-repeated call, so reduce clutter with var int length = s.length(); if (length <= 1) return s; else return s.substring(length - 1) + reverse(s.substring(0, length - 1)); } }
正如Mehrdad所指出的，最好不要使用递归。 但是，如果你确实使用它，那么你可以同时保留每次调用的第一个和最后一个字符，从而将递归调用的数量减半。 那是，
public String reverseString(String s){ int len = s.length(); if (len <= 1) { return s; } char fst = s.charAt(0); char lst = s.charAt(len - 1); return lst + reverseString(s.substring(1, len - 2)) + fst; }
这也处理空字符串的情况。 也许传递具有适当容量的StringBuilder会加快速度，但这仍然是读者的练习;）
您可以尝试使用外部变量，并逐个添加1个字符：
public static String back=""; public static String reverseString(String str){ if(str.length()==0){ return back; }else { back+=str.charAt(str.length()-1); lees(str.substring(0,str.length()-1)); return back; }
}
这是我的不可变版本：
String reverse(String str) { if(str.length()<2) return str; return reverse(str.substring(1)) +str.charAt(0); }
和尾递归版：
String reverseTail(String str) { if(str.length()<2) return str; return str.charAt(str.length()-1)+ reverseTail(str.substring(0,str.length()-1));
在这种情况下，这是完全没必要的，但是如果你自己创建堆栈，你可以模拟递归并避免递归深度问题。
您可以迭代实现递归，当您拥有本质上递归的算法时，这可能是必要的，但是也需要针对大问题大小运行它们。
String recIterReverse (String word){ Stack stack = new Stack (); stack.push(word); String result = ""; while (!stack.isEmpty()){ String temp = stack.pop(); result = temp.charAt(0) + result; if (temp.length() > 1){ stack.push(temp.substring(1)); } } return result; }
function调用：
//str:string to be reversed,i=0,j=str.length-1 public void reverseString(String str,int i,int j) { if(i==j) { System.out.println(str); return; } char x=str.charAt(i); str=str.replace(str.charAt(i),str.charAt(j)); str=str.replace(str.charAt(j),x); i++;j--; reverseString(str,i,j); }
这种方法也有效..
请尝试以下方法：
public class reverse2 { public static void main(String name) { String revname=new StringBuffer(name).reverse().toString(); System.out.println("original string " + name + " and the reverse of it is " + revname); } }
public static String rev(String name){ if(name.length()>=1){ System.out.print(name.charAt(name.length()-1)); return rev(name.substring(0,name.length()-1)); } else{ return ""+name.substring(0); } }
String rev=""; public String reverseString(String s){ if (s.length()==0) return ""; return rev+s.substring(s.length()-1,s.length())+reverseString(s.substring(0, s.length()-1)); }
public String reverseString (String s) { if (s != null && s.length () > 0 ) { rev = rev + s.substring (s.length () - 1); reverseString (s.substring (0, s.length () - 1)); } return rev; }
public class StringUtility { public static void main(String[] args) { StringUtility stringUtility = new StringUtility(); String input = "santosh123"; int middle = input.length() / 2; middle = middle - 1; System.out.println(stringUtility.stringReverse(input, middle)); } public String stringReverse(String input, int middle) { if (middle == -1) { System.out.println("if"); return input; } else { System.out.println("else"); input = swapChar(input, middle); middle = middle - 1; return stringReverse(input, middle); } } private String swapChar(String input, int middle) { StringBuilder str = new StringBuilder(input); char begin = str.charAt(middle); int endIndex = input.length() - middle - 1; char end = str.charAt(endIndex); str.setCharAt(middle, end); str.setCharAt(endIndex, begin); System.out.println(str + " " + middle + " " + endIndex); return str.toString(); } }
如果你觉得代码越少越好……
static String reverse(String str){ return str.length()>=2 ? str.charAt(str.length()-1) + reverse(str.substring(0,str.length()-1)) : str ; }
已经有大约20个答案，但我也会抛出我的递归算法。 它可能有点冗长，但它至少是可读的。
public static String reverseString(String str) { return reverseString("", str); } private static String reverseString(String result, String original) { if (original.length() == 0) { return result; } else { int length = original.length(); String lastLetter = original.substring(length - 1, length); original = original.substring(0, length - 1); return reverseString(result + lastLetter, original); } }
代码基本上递归地获取字符串的结尾并将其移到前面。 例如，如果我们想要反转的字符串是“jam”，那么每次调用helper方法时，结果和原始字符串如下：
// result: original: // "" jam // m ja // ma j // maj ""
使用递归方法调用反向字符串。
示例代码
public static String reverseString(String s) { if (s.length() == 0) { return s; } else { return s.charAt(s.length() - 1) + reverseString(s.substring(0, s.length() - 1)); } }
这是我的解决方案，我在上面的许多解决方案中看到我们得到的字符串长度，但理想情况下我们不需要它。 Zen是使用递归，只需要切掉字符串的第一个字符串，然后将其余字符传递给递归方法。 好极了！！ 我们得到了解决方案。
private static void printReverse(String str) { if (!str.isEmpty()) { String firstChar = str.substring(0, 1); //Get first char of String String newstr = str.substring(0, 0) + str.substring(1); // Get remaining string printReverse(newstr); // Recursion magic System.out.print(firstChar); //Output } }
public static String reverse(String s){ int n = s.length()-1; if(n >=0) return s.substring(s.length()-1)+ReverseString(s.substring(0,n--)); else return ""; }