java - 我在java中的这个递归函数中缺少什么

Question

所以我有这个作业(我不是想作弊)，我在类论坛上提出了这个问题，但我很难理解教授写的伪代码......它是如何工作的。

目标是获取字符串列表和“r”，“w”，“b”... 然后将它们重新排序为 6 个新字符串...

这是我根据他的伪代码编写的java:

public class Solution2 {
    public static ArrayList<String> solve(ArrayList<String> base) {

        ArrayList<String> temp = new ArrayList<String>();
        ArrayList<String> result = new ArrayList<String>();
        // Check for the empty set
        if (base == null) {
            ArrayList<String> empty = new ArrayList<String>();
            return empty;
        }

        char first = 'y';
        String firstString = "";
        for (Iterator<String> i = base.iterator(); i.hasNext();) {

            if (first == 'y') {
                firstString = i.next();
                base.remove(0);
                first = 'n';
            }

            temp = solve(base);

            for (Iterator<String> n = temp.iterator(); n.hasNext();) {
                // Add first string
                result.add(firstString + n.next());
            }

            return result;
            //

        }
        return result;
    }
}

我只是不知道你是如何不断积累主要字符串列表的。我得到一个空集......这是基本情况。

Answer 1

我认为在尝试理解教授的代码之前，您应该备份并考虑一个更简单的情况，这样您就知道要寻找什么。

您的递归函数需要一个步骤，返回一个列表，其中添加了新元素以及下一个递归调用的结果。

假设我们有一个函数，我们返回一个由列表中的单独字符组成的列表:

static List<String> listChars(String s) {
    if ("".equals(s)) return new ArrayList<String>();
    List<String> ret = new ArrayList<>();
    ret.add(s.substring(0,1));
    ret.addAll(listChars(s.substring(1)));
    return ret; 
}

测试工具看起来像

public static void main(String[] args) {
    System.out.println("result of '' =" + listChars(""));
    System.out.println("result of 'a'=" + listChars("a"));
    System.out.println("result of 'abcd'=" + listChars("abcd"));
}

打印内容

result of '' =[]
result of 'a'=[a]
result of 'abcd'=[a, b, c, d]

您的函数不存在这样的情况:您将当前迭代的结果加上下一次递归调用的结果添加到您要返回的列表中。