时间戳

首页 > 解决方案 > 在 Java 中使用回溯递归打印字符串的所有子序列

java - 在 Java 中使用回溯递归打印字符串的所有子序列

问题描述

我知道这是一个在这里被问了很多的问题，网上有很多例子，但我没有找到一个与我的问题相匹配的例子。

我需要编写一个代码来接收一个字符串，并按照它们在单词中出现的顺序打印所有不同的子序列。该解决方案应该只有递归方法，根本没有循环。（显然应该基于回溯递归和数组或子字符串）

例如“012”应该打印：“0”、“1”、“2”、“01”、“12”、“02”、“012”

起初我打算这样做：

public static void printSubs(String s) {
    printSubsSol(s, "");
}

private static void printSubsSol(String s, String temp) {
    if (s.length()==0) {
        System.out.print(temp+" ");
        return;
    }
    printSubsSol(s.substring(1), temp);
    printSubsSol(s.substring(1),temp+s.charAt(0));
}

打印：2 1 12 0 02 01 012

我无法以正确的顺序打印所有子序列，所以现在我尝试了一种使用 char 数组的不同方法，但我还没有成功

public class Ex9Q2V4 {
public static void printSubs(String s) {
    char[] tempArr = new char[s.length() - 1];
    printSubsSol(s, 0, 0, tempArr, 1);
    System.out.println('"' + s + '"');
}

private static boolean isSafe(int arrayIndex, int currentIndex, int howMuchToPrint, int length) {
    return (arrayIndex < howMuchToPrint && arrayIndex <= currentIndex && currentIndex < length);
}

private static void printSubsSol(String s, int arrayIndex, int currentIndex, char[] charArr, int howMuchToPrint) {
    if (howMuchToPrint == s.length()) {
        return;
    }
    charArr[arrayIndex] = s.charAt(currentIndex);
    if (arrayIndex == howMuchToPrint - 1) {
        System.out.print("\"");
        printArray(charArr, howMuchToPrint);
        System.out.print("\"" + ", ");
    }
    if (isSafe(arrayIndex + 1, currentIndex + 1, howMuchToPrint, s.length())) {
        printSubsSol(s, arrayIndex + 1, currentIndex + 1, charArr, howMuchToPrint);

    }
    else if (isSafe(arrayIndex, currentIndex + 1, howMuchToPrint, s.length())) {
        printSubsSol(s, arrayIndex, currentIndex + 1, charArr, howMuchToPrint);

    }
    else printSubsSol(s, 0, 0, charArr, howMuchToPrint + 1);
}

// A method that prints the array
private static void printArray(char arr[], int n) {
    if (n != 0) {
        printArray(arr, n - 1);
        System.out.print(arr[n - 1]);
    }
}

}

打印：“0”、“1”、“2”、“01”、“02”、“12”、“012”

如果可能的话，我很乐意以两种方式看到解决方案。

标签： javarecursionbacktracking

解决方案

让我们看看循环

for (int i = 1; i <= s.length(); i++) {
     for (int j = 0; j + i <= s.length(); j++) {
          System.out.print(s.substring(j, j + i) + " ");
     }
}

你的第二个想法走在正确的轨道上，你需要一个索引和一个长度，但它似乎过于复杂。

static void print(String s, int start, int length) {
    System.out.print(s.substring(start, start + length) + " ");
    if (start + length < s.length())
        print(s, start + 1, length);
    else if (length < s.length())
        print(s, 0, length + 1);
}

首先我们打印子字符串。

if条件是嵌套循环，如果开始索引+要打印的长度仍然低于字符串的长度，我们只是增加开始索引

else 部分是第一个循环，当您到达输入字符串的末尾并且不能再使用子字符串时，您将起始索引设置回 0 并增加长度。如果长度等于输入的长度，递归停止

当然你应该先检查输入是否为空

推荐阅读