java - 关于java递归创建字符串组合

Question

问题是要求我返回包含给定长度 n 的由“cc”和“ddd”组成的所有可能的字符串组合的集合。

例如，如果给定的长度为 5，则设置将包括“ccddd”和“dddcc”。长度为 6 将返回包含“cccccc”、“dddddd”的集合
长度为 7 将返回包含“ccdddcc”、“dddcccc”、“ccccddd”的集合长度为 12 将返回 12 种不同的组合，依此类推

但是，返回的集合为空。你能帮忙吗？

“请理解极差的编码风格”

public static Set<String> set = new HashSet<String>();

public static Set<String> generateset(int n) {


    String s = strings(n,n,"");


    return set; // change this
}

public static String strings(int n,int size, String s){


    if(n == 3){
        s = s + ("cc");
        return "";}
    if(n == 2){
        s = s + ("ddd");
        return "";}
    if(s.length() == size)
        set.add(s);

    return strings(n-3,size,s) + strings(n-2,size,s); 
}

Answer 1

我认为您需要重新考虑您的方法。这不是一个简单的问题，因此，如果您对 Java 非常陌生(并且对其他编程语言不太熟悉)，那么在解决此类问题之前，您可能需要尝试一些涉及集合、列表或其他集合的更简单的问题。

假设您无论如何都想尝试一下:像这样的递归问题需要非常清楚地思考您希望如何完成任务。我想你已经有了一个大概的想法，但还需要更清晰。以下是我解决这个问题的方法:

(1) 您需要一个返回长度为 N 的字符串列表(或集合)的方法。您的递归方法返回单个 String，据我所知，您对结果字符串没有明确的定义。 (清晰的定义在编程中非常重要，但在解决复杂的递归问题时可能更是如此。)

(2) 字符串将以 "cc" 或 "ddd" 开头。因此，要形成结果列表，您需要:

(2a) 查找长度为 N-2 的所有字符串。这是您需要递归调用来获取该长度的所有字符串的地方。遍历该列表中的所有字符串，并将 "cc" 添加到每个字符串的前面。

(2b) 同样，通过递归调用查找长度为 N-3 的所有字符串；遍历该列表中的所有字符串，并将 "ddd" 添加到前面。

(2c) 结果列表将是步骤 (2a) 和 (2b) 中的所有字符串。

(3) 您需要基本案例。如果 N 为 0 或 1，则结果列表将为空。如果 N==2，则只有一个字符串，"cc"；如果 N==3，则只有一个字符串，"ddd"。

如果需要，您可以使用Set而不是列表，因为顺序并不重要。

请注意，使用全局列表或集合来保存结果不是一个好主意。当一个方法递归地调用自身，并且该方法的每次调用都触及相同的列表或集合时，你会疯狂地试图让一切正常工作。如果让每个递归调用保存其自己的本地列表和结果，那就容易多了。 编辑:这需要澄清。使用全局(即由所有递归调用共享的实例字段)集合来保存最终结果是可以的。但我上面概述的方法涉及很多中间结果——即如果你想查找长度为 8 的所有字符串，那么你还将查找长度为 6, 5, 4, ... 的字符串；使用全局来保存所有这些将是痛苦的。