在核心 Java 中使用递归机制在另一个字符串中查找字符串
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4530449/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding a String in another String Using Recursion Mechanism in Core Java
提问by Deepak
I have the below Problem Statement
我有以下问题陈述
PS: Given a string "str" and a Non-Empty substring "sub" ,compute "Recursively" if at least "N" copies of "sub" appear in the "string somewhere", possibly with "Overlapping". N will be non-negative.
PS：给定一个字符串“str”和一个非空子字符串“sub”，如果“sub”的至少“N”个副本出现在“字符串某处”中，可能带有“重叠”，则计算“递归”。N 将是非负的。
Example are as shown belowstrCopies("catcowcat", "cat", 2) → truestrCopies("catcowcat", "cow", 2) → falsestrCopies("catcowcat", "cow", 1) → truestrCopies("iiijjj", "ii", 2) → true
Example are as shown belowstrCopies("catcowcat", "cat", 2) → truestrCopies("catcowcat", "cow", 2) → falsestrCopies("catcowcat", "cow", 1) → truestrCopies("iiijjj", "ii", 2) → true
I have written the code as shown below(without recursion) and is working fine for few test cases,except for others which are marked as FAIL.
我已经编写了如下所示的代码（没有递归）并且对于少数测试用例运行良好，除了其他标记为 FAIL 的测试用例。
:::Code is as shown below:::
:::代码如下图:::
public boolean strCopies(String str, String sub, int n) {
int len = sub.length();
int result=0;
if(len>0){
int start = str.indexOf(sub);
while(start !=-1){
result++;
start = str.indexOf(sub,start+len);
}
}
if(result==n){
return true;
}else return false;
}
Runs for above code as shown below(Marked in BOLD are FAILED TEST CASES)
运行上面的代码，如下所示（用粗体标记的是失败的测试用例）
Expected This RunstrCopies("catcowcat", "cat", 2) → true true OKstrCopies("catcowcat", "cow", 2) → false false OKstrCopies("catcowcat", "cow", 1) → true true OKstrCopies("iiijjj", "ii", 2) → true false FAILstrCopies("iiiiij", "iii", 3) → true false FAILstrCopies("ijiiiiij", "iiii", 2) → true false FAIL
Expected This RunstrCopies("catcowcat", "cat", 2) → true true OKstrCopies("catcowcat", "cow", 2) → false false OKstrCopies("catcowcat", "cow", 1) → true true OKstrCopies("iiijjj", "ii", 2) → true false FAILstrCopies("iiiiij", "iii", 3) → true false FAILstrCopies("ijiiiiij", "iiii", 2) → true false FAIL
Could you check and let me know what is wrong with the code for FAIL TEST CASES ?Im unable to consider the Overlapping scenarios.
你能检查一下并让我知道 FAIL TEST CASES 的代码有什么问题吗？我无法考虑重叠场景。
回答by Jon Skeet
Well, your first problem is that your method isn't recursive. I suspect you want to work with substringas well as indexOf...
好吧，你的第一个问题是你的方法不是递归的。我怀疑你想substring和indexOf...一起工作
As for why your current method isn't working, I suspect it's because you're using start + leninstead of start + 1to find the next starting position. So when trying to find "ii" in "iii", you should first look at position 0, then position 1 - currently you're looking at position 2, which would mean it wouldn't find the second "ii" starting at 1.
至于为什么您当前的方法不起作用，我怀疑是因为您正在使用start + len而不是start + 1找到下一个起始位置。因此，当试图在“iii”中找到“ii”时，您应该首先查看位置 0，然后查看位置 1——目前您正在查看位置 2，这意味着它不会找到从 1 开始的第二个“ii” .
回答by aioobe
First of all, your solution is not recursive (strCopiesdoes not call itself).
首先，您的解决方案不是递归的（strCopies不调用自身）。
Here is a suggestion for a recursive version of your algorithm:
以下是对算法递归版本的建议：
public static boolean strCopies(String str, String sub, int n) {
if (str.isEmpty())
return n == 0;
int remainingN = str.startsWith(sub) ? n - 1 : n;
return strCopies(str.substring(1), sub, remainingN);
}
Btw, note that your last lines of code:
顺便说一句，请注意您的最后几行代码：
if(result==n)
return true;
else
return false;
can always be replaced with simply
总是可以简单地替换
return result == n;
回答by Gondim
public class StackOverflow {
public static void main(String[] args) {
String string = "catcowcat";
String substring = "cat";
System.out.println(string + " has " + findNumberOfStrings(string, substring, 0) + " " + substring);
}
private static int findNumberOfStrings(String string, String substring, int count){
if (string.length() == 0){
return count + 0;
}
if (string.length() < substring.length()){
return count + 0;
}
if (string.contains(substring)){
count++;
string = string.replaceFirst(substring, "");
return findNumberOfStrings(string, substring, count);
}
return count;
}
}
回答by Kahini Wadhawan
The pure recursion code for the problem is:
该问题的纯递归代码是：
public boolean strCopies(String str, String sub, int n) {
if(n==0) return true;
if(str.length()==0) return false;
if(str.length()<sub.length()) return false;
if(str.startsWith(sub)) return strCount(str.substring(1),sub, n, 1);
return strCopies(str.substring(1),sub,n);
}
public boolean strCount(String str , String sub , int n , int count ) {
if( count>= n) return true;
if(str.length()==0) return false;
if(str.length()<sub.length()) return false;
if(str.startsWith(sub)) {
count++;
if( count>= n) return true;
}
return strCount(str.substring(1),sub, n , count );
}
We have to maintain a count of occurrences of sub in str string. But in recursive call of strCopies function if we take count variable, everytime function is called the value of var count will reinitialize (we cannot maintain count in memory of function and cannot keep on adding to its previous value). So for maintaining the value of count we pass the value of count to another function strCount (as return strCount(str.substring(1), sub, n, count ) )which also works recursively and can do count++, as it is called with a value of count only and count doesnot get reintialized rather get carried forward.
我们必须维护一个 sub 在 str 字符串中出现的次数。但是在 strCopies 函数的递归调用中，如果我们使用 count 变量，每次调用函数时，var count 的值都会重新初始化（我们无法在函数的内存中维护 count 并且无法继续添加到其先前的值）。因此，为了维护 count 的值，我们将 count 的值传递给另一个函数 strCount （因为return strCount(str.substring(1), sub, n, count ) )它也可以递归工作并且可以执行 count++，因为它仅使用 count 值调用，并且 count 不会重新初始化，而是继续进行。
回答by user847988
The basic idea is that you search for the index of the sub word and then you send the new string which is starting one character after the index you have found the word since you allow overlapping.
基本思想是您搜索子词的索引，然后发送新字符串，该字符串在您找到该词的索引之后的一个字符开始，因为您允许重叠。
public boolean strCopies(String str, String sub, int n) {
if (str == null || str.equals("") || str.length() < sub.length())
if (n == 0)
return true;
else
return false;
int index = str.indexOf(sub);
if (index != -1)
return false || strCopies(str.substring(index + 1),sub,--n);
else
return false || strCopies("",sub,n);
}
