英文:
String Recursion Method in Java
问题
我正在尝试编写一个递归程序:计算所有长度为n
的字符串,这些字符串可以由string
中提供的所有字符组成,但不允许出现在sub
中列出的任何字符串作为子字符串。
这是我目前编写的程序,但它尚未实现sub
的限制,它只计算了string
的排列。
public static void method(String string)
{
method(string, "");
}
public static void method(String string, String soFar)
{
if (string.isEmpty())
{
System.err.println(soFar + string);
}
else
{
for (int i = 0; i < string.length(); i++)
{
method(string.substring(0, i) + string.substring(i + 1, string.length()), soFar + string.charAt(i));
}
}
}
英文:
I'm trying to write a recursive program: to compute all strings of length n
that can be formed from all the characters given in string
, but none of the strings listed in sub
are allowed to appear as substrings.
This is the program I have written so far, but it doesn't yet implement the restriction of sub
, it only computes the permutations of string
.
public static void method(String string)
{
method(string, "");
}
public static void method(String string, String soFar)
{
if (string.isEmpty())
{
System.err.println(soFar + string);
}
else
{
for (int i = 0; i < string.length(); i++)
{
method(string.substring(0, i) + string.substring(i + 1, string.length()), soFar + string.charAt(i));
}
}
}
答案1
得分: 2
从你的示例中我看出你想要生成所有包含重复的n
个字符的排列,但是你的代码生成了所有不重复字符的排列。根据示例,以下代码应该解决你的问题:
public static List<String> method(String string, int n, List<String> sub)
{
List<String> results = new ArrayList<>();
method(string, n, "", sub, results);
return results;
}
private static void method(String string, int n, String soFar, List<String> sub, List<String> results)
{
for (String s: sub)
{
if(soFar.length() >= s.length() && soFar.substring(soFar.length() - s.length()).equals(s))
{
return;
}
}
if (soFar.length() == n)
{
results.add(soFar);
}
else
{
for (int i = 0; i < string.length(); i++)
{
method(string, n, soFar + string.charAt(i), sub, results);
}
}
}
此外,当string
为空时,追加string
是多余的。
英文:
From your example I see that you want all permutations with repetition for n
characters, but your code generates all permutations without repetition for all characters.
This should solve your problem as stated in the example:
public static List<String> method(String string, int n, List<String> sub)
{
List<String> results = new ArrayList<>();
method(string, n, "", sub, results);
return results;
}
private static void method(String string, int n, String soFar, List<String> sub, List<String> results)
{
for (String s: sub)
{
if(soFar.length() >= s.length() && soFar.substring(soFar.length() - s.length()).equals(s))
{
return;
}
}
if (soFar.length() == n)
{
results.add(soFar);
}
else
{
for (int i = 0; i < string.length(); i++)
{
method(string, n, soFar + string.charAt(i), sub, results);
}
}
}
Also, it's redundant to append string
when string
is empty.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论