Finding a String in another String Using Recursion Mechanism in Core Java

Question

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.

Example are as shown below
strCopies("catcowcat", "cat", 2) → true
strCopies("catcowcat", "cow", 2) → false
strCopies("catcowcat", "cow", 1) → true
strCopies("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.

:::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 Run
strCopies("catcowcat", "cat", 2) → true true OK
strCopies("catcowcat", "cow", 2) → false false OK
strCopies("catcowcat", "cow", 1) → true true OK
strCopies("iiijjj", "ii", 2) → true false FAIL
strCopies("iiiiij", "iii", 3) → true false FAIL
strCopies("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.

Jon Skeet · Accepted Answer · 2010-12-25 14:03:07Z

3

Well, your first problem is that your method isn't recursive. I suspect you want to work with substring as well as indexOf...

As for why your current method isn't working, I suspect it's because you're using start + len instead of start + 1 to 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.

answered Dec 25, 2010 at 14:03

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Deepak Over a year ago

what fix is required for the program in order to work for FAIL test cases.

Jon Skeet Over a year ago

@Deepak: I'm not just going to give you the code, as this is clearly a homework exercise (and one which has nothing to do with arrays - I'm not sure why you've tagged it that way). I've explained what's wrong with your current code, and also suggested that you should use recursion as per the instructions. If you have trouble understanding what I've written, please say so - but I'm not going to just do your homework for you. That wouldn't help anyone.

aioobe · Accepted Answer · 2010-12-25 14:10:38Z

2

First of all, your solution is not recursive (strCopies does not call itself).

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);
}

(All your test-cases pass.)

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;

edited Dec 25, 2010 at 14:10

answered Dec 25, 2010 at 14:05

aioobe

423k115 gold badges831 silver badges844 bronze badges

Comments

Gondim · Accepted Answer · 2010-12-25 14:58:52Z

1

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;
 }

}

answered Dec 25, 2010 at 14:58

Gondim

3,0588 gold badges48 silver badges62 bronze badges

Comments

Peter O. · Accepted Answer · 2012-10-11 14:55:21Z

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.

user847988 · Accepted Answer · 2013-03-02 13:54:03Z

0

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);

}

answered Mar 2, 2013 at 13:54

user847988

9941 gold badge16 silver badges30 bronze badges

Collectives™ on Stack Overflow

Finding a String in another String Using Recursion Mechanism in Core Java

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related