使用递归来反转字符串

Question

我正在尝试使用递归逐字反转字符串。（例如："Hello my friend" 反转为 "friend my Hello"）这是我尝试为此方法编写的代码。我尝试了多种类似的变体，但输出只是字符串的第一个或最后一个字。我相信 "broken" 部分是第一个 if 语句，但我不太确定。

public static String reverse (String words) {
   Scanner sc = new Scanner(words);
   String backwards = "";

   if (sc.hasNext()) {
     String currentWord = sc.next();
     reverse(sc.nextLine());
     backwards = backwards + " " + currentWord;
   } //end if
   else {
     backwards = words;
   } //end else

   return backwards;
 }

我知道存在一些类似的问题，但他们的回答似乎无法帮助我理解我的错误。

谢谢！

Answer 1

一定要用递归吗？没有它你也可以做到。

public static String reverse(String words) {
    String[] list = words.split(" ");
    Collections.reverse(list);
    String reversed = String.join(" ", list);
    return reversed;
}

Answer 2

如评论中所述，您可以使用 StringBuilder 而不是扫描仪 class。

此示例发送相同的词，每次您输入该方法时将它们用空格分开，并发送要在下一次迭代中添加的词的索引。

例如：

public class RecursiveReverse {

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        String stringToReverse = "Hello my friend!";
        System.out.println(reverse(stringToReverse, stringToReverse.split(" ").length - 1));
    }

    public static String reverse(String words, int i) {
        if (i >= 0) { //If the index of the words is greater or equals the first word
            sb.append(words.split(" ")[i]); //We split it and append it to our StringBuilder
            sb.append(" "); //We append a space
            reverse(words, --i); //We do this again
        }
        return sb.toString(); //When the above condition doesn't match we return the StringBuilder object as a String (which contains the words reversed)
    }
}

产生此输出：

friend! my Hello

更好的方法是将字符串数组作为参数传递，这样您只拆分一次字符串（当将单词作为数组发送到方法时）。

public class RecursiveReverse {

    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        String stringToReverse = "Hello my friend!";
        String words[] = stringToReverse.split(" ");
        System.out.println(reverse(words, words.length - 1));
    }

    public static String reverse(String words[], int i) {
        if (i >= 0) {
            sb.append(words[i]);
            sb.append(" ");
            reverse(words, --i);
        }
        return sb.toString();
    }
}

Answer 3

你丢弃了递归结果：

 reverse(sc.nextLine());
 backwards = backwards + " " + currentWord;

改为使用：

 backwards = reverse(sc.nextLine());
 backwards = backwards + " " + currentWord;

更好的是：

 backwards = reverse(sc.nextLine()) + " " + currentWord;

Answer 4

您必须在累加器中保留调用之间提取的单词。这是一个例子。

public static String reverse(String words, String acc){
    Scanner sc = new Scanner(words);

    if(!sc.hasNext()){
        return acc;
    }

    return reverse(sc.nextLine(), acc) + " " + sc.next();
}

你可以这样称呼它。

reverse("Hello my friend", "");

这不是世界上最有效的实施方式，但是是的...它一定有效！

如果您想要更高效的，请使用 StringBuilder 作为累加器。

Answer 5

您不应该调用 nextLine()，因为您的输入全部在一行中。如果您从创建一个简单的辅助方法开始，您的逻辑就会清晰得多，它应该采用 words 数组和一个位置；从那里你可以递归地构建你想要的输出，比如

private static String reverse(String[] words, int p) {
    if (p + 1 < words.length) {
        return reverse(words, p + 1) + " " + words[p];
    } else if (p < words.length) {
        return words[p];
    }
    return "";
}

那么你的public方法很容易实现，只需split白色的原始输入space并从0开始调用reverse（记住return 结果）。喜欢，

public static String reverse(String words) {
    return reverse(words.split("\s+"), 0);
}

然后，我测试了一下

public static void main(String[] args) {
    System.out.println(reverse("Hello my friend"));
}

哪些输出（按要求）

friend my Hello

或者，你可以让那个帮手拿你的 Scanner 而不是

private static String reverse(Scanner sc) {
    if (sc.hasNext()) {
        String currentWord = sc.next();
        if (sc.hasNext()) {
            return reverse(sc) + " " + currentWord;
        }
        return currentWord;
    }
    return "";
}

然后你的public方法是

public static String reverse(String words) {
    return reverse(new Scanner(words));
}

Answer 6

您可以使用 String.split 的重载来围绕第一个 space:

拆分 words，而不是使用 Scanner

public static String reverse(String words) {
    String[] wordArr = words.split(" ", 2); // split into a maximum of 2 Strings

    if (wordArr.length > 1) { // If there is more than 1 word
        // return the first word (wordArr[0]),
        // behind the reverse of the rest of the String (wordArr[1])
        return reverse(wordArr[1]) + " " + wordArr[0];
    }

    return wordArr[0]; // else, just return the one word
}

Answer 7

public static String reverseSentence(String sentence) {

    StringBuilder sb = new StringBuilder();

    int firstSpace = sentence.indexOf(' ');
    if (firstSpace == -1) {
        return sb.append(sentence.strip()).append(" ").toString();
    }
    String secondPart = sentence.substring(firstSpace + 1); 
    String firstPart = sentence.substring(0, firstSpace);//similar to merger sort 
    return sb.append(reverseSentence(secondPart)).append(reverseSentence(firstPart)).toString();
}

使用递归来反转字符串

Using Recursion to Reverse a String

java

string

recursion

reverse