字符串递归方法在Java中

huangapple go评论73阅读模式
英文:

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, &quot;&quot;);
    }
    public static void method(String string, String soFar)
    {
        if (string.isEmpty())
        {
            System.err.println(soFar + string);
        }
        else
        {
            for (int i = 0; i &lt; 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&lt;String&gt; method(String string, int n, List&lt;String&gt; sub)
    {
        List&lt;String&gt; results = new ArrayList&lt;&gt;();
        method(string, n, &quot;&quot;, sub, results);
        return results;
    }
    private static void method(String string, int n,  String soFar, List&lt;String&gt; sub, List&lt;String&gt; results)
    {
        for (String s: sub)
        {
            if(soFar.length() &gt;= s.length() &amp;&amp; soFar.substring(soFar.length() - s.length()).equals(s))
            {
                return;
            }
        }
        if (soFar.length() == n)
        {
            results.add(soFar);
        }
        else
        {
            for (int i = 0; i &lt; string.length(); i++)
            {
                method(string, n, soFar + string.charAt(i), sub, results);
            }
        }
    }

Also, it's redundant to append string when string is empty.

huangapple
  • 本文由 发表于 2020年3月15日 22:29:50
  • 转载请务必保留本文链接:https://go.coder-hub.com/60693943.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定