字符串递归方法在Java中

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

String Recursion Method in Java

问题

我正在尝试编写一个递归程序：计算所有长度为n的字符串，这些字符串可以由string中提供的所有字符组成，但不允许出现在sub中列出的任何字符串作为子字符串。

这是我目前编写的程序，但它尚未实现sub的限制，它只计算了string的排列。

  1. public static void method(String string)
  2. {
  3.     method(string, "");
  4. }
  5. public static void method(String string, String soFar)
  6. {
  7.     if (string.isEmpty())
  8.     {
  9.         System.err.println(soFar + string);
  10.     }
  11.     else
  12.     {
  13.         for (int i = 0; i < string.length(); i++)
  14.         {
  15.             method(string.substring(0, i) + string.substring(i + 1, string.length()), soFar + string.charAt(i));
  16.         }
  17.     }
  18. }
英文:

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.

  1.     public static void method(String string)
  2.     {
  3.         method(string, &quot;&quot;);
  4.     }
  5.     public static void method(String string, String soFar)
  6.     {
  7.         if (string.isEmpty())
  8.         {
  9.             System.err.println(soFar + string);
  10.         }
  11.         else
  12.         {
  13.             for (int i = 0; i &lt; string.length(); i++)
  14.             {
  15.                 method(string.substring(0, i) + string.substring(i + 1, string.length()), soFar + string.charAt(i));
  16.             }
  17.         }
  18.     }

答案1

得分: 2

从你的示例中我看出你想要生成所有包含重复的n个字符的排列，但是你的代码生成了所有不重复字符的排列。根据示例，以下代码应该解决你的问题：

  1. public static List<String> method(String string, int n, List<String> sub)
  2. {
  3.     List<String> results = new ArrayList<>();
  4.     method(string, n, "", sub, results);
  5.     return results;
  6. }
  7. private static void method(String string, int n,  String soFar, List<String> sub, List<String> results)
  8. {
  9.     for (String s: sub)
  10.     {
  11.         if(soFar.length() >= s.length() && soFar.substring(soFar.length() - s.length()).equals(s))
  12.         {
  13.             return;
  14.         }
  15.     }
  16.     if (soFar.length() == n)
  17.     {
  18.         results.add(soFar);
  19.     }
  20.     else
  21.     {
  22.         for (int i = 0; i < string.length(); i++)
  23.         {
  24.             method(string, n, soFar + string.charAt(i), sub, results);
  25.         }
  26.     }
  27. }

此外，当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:

  1.     public static List&lt;String&gt; method(String string, int n, List&lt;String&gt; sub)
  2.     {
  3.         List&lt;String&gt; results = new ArrayList&lt;&gt;();
  4.         method(string, n, &quot;&quot;, sub, results);
  5.         return results;
  6.     }
  7.     private static void method(String string, int n,  String soFar, List&lt;String&gt; sub, List&lt;String&gt; results)
  8.     {
  9.         for (String s: sub)
  10.         {
  11.             if(soFar.length() &gt;= s.length() &amp;&amp; soFar.substring(soFar.length() - s.length()).equals(s))
  12.             {
  13.                 return;
  14.             }
  15.         }
  16.         if (soFar.length() == n)
  17.         {
  18.             results.add(soFar);
  19.         }
  20.         else
  21.         {
  22.             for (int i = 0; i &lt; string.length(); i++)
  23.             {
  24.                 method(string, n, soFar + string.charAt(i), sub, results);
  25.             }
  26.         }
  27.     }

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
  • java
  • recursion
  • string
  • substring
匿名

发表评论

匿名网友

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

确定