Java > Recursion-1 > strCopies (CodingBat Solution)

Problem:

Given a string 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.

strCopies("catcowcat", "cat", 2) → true
strCopies("catcowcat", "cow", 2) → false
strCopies("catcowcat", "cow", 1) → true


Solution:

public boolean strCopies(String str, String sub, int n) {
  if (func(str, sub) == n) return true;
  else return false;
}

private int func(String str, String sub) {
  int strlen = str.length();
  int sublen = sub.length();
  if (strlen < sublen) return 0;
  if (str.substring(0, sublen).equals(sub))
    return 1 + func(str.substring(1), sub);
  else
    return func(str.substring(1), sub);
}


10 comments :

  1. public boolean strCopies(String str, String sub, int n) {
    if(n == 0)
    return true;
    if(str.length() < sub.length())
    return false;
    if(str.substring(0,sub.length()).equals(sub))
    return strCopies(str.substring(1), sub, n-1);
    return strCopies(str.substring(1), sub, n);
    }

    ReplyDelete
    Replies
    1. Above soln is not correct, as if called with n=0 then it will fail. Eg: strCopies("iiijjj", "ii", 0)

      Better solution is:
      public boolean strCopies(String str, String sub, int n) {
      if (str.length()<sub.length()) {
      if (n == 0)
      return true;
      else
      return false;
      }
      else if (str.substring(0, sub.length() ).equals(sub))
      return strCopies(str.substring(1), sub, --n);
      return strCopies(str.substring(1), sub, n);
      }

      Delete
  2. public boolean strCopies(String str, String sub, int n) {
    if(str.indexOf(sub)==-1 && n==0) return true;
    if(str.indexOf(sub)!=-1)
    {
    return strCopies(str.substring(str.indexOf(sub)+1), sub, n-1);
    }
    return false;
    }

    ReplyDelete
  3. I came up with this code..

    int count;
    public boolean strCopies(String str, String sub, int n) {
    if (str.indexOf(sub) != -1) {
    count++;
    strCopies(str.substring(str.indexOf(sub)+1), sub, n);
    }
    if (count == n) {
    return true;
    }
    else {
    count = 0;
    return false;
    }
    }

    However it does not work with the case
    strCopies("iiijjj", "i", 3)

    Although in eclipse it returns true in coding bat the return value is false..Any ideas?

    ReplyDelete
    Replies
    1. Fixed it:

      boolean match;
      public boolean strCopies(String str, String sub, int n) {
      if (n == 0) {
      match = true;
      }
      if (str.indexOf(sub) != -1) {
      match = false;
      n--;
      strCopies(str.substring(str.indexOf(sub)+1), sub, n);
      }
      return match;
      }

      Delete
  4. public boolean strCopies(String str, String sub, int n) {
    if(n==0&&str.equals("")){
    return true;
    }
    else if(str.indexOf(sub)==0){
    return strCopies(str.substring(1),sub,n-1);
    }
    else if(str.indexOf(sub)!=0&& !str.equals("")){
    return strCopies(str.substring(1),sub,n);
    }
    else{
    return false;
    }
    /*Sometiems you need more trial and error. What helped was
    *figuring out which arguement(s) were important so that I
    *could make a proper base case.
    */
    }

    ReplyDelete
  5. public boolean strCopies(String str, String sub, int n) {

    int idx = str.indexOf(sub);

    if (n==0 && idx==-1)
    return true;

    if (n>0 && idx==-1)
    return false;

    if (n==0 && idx>=0)
    return false;

    return strCopies((str.substring(0, idx) + str.substring(idx+1)), sub, --n);

    }

    ReplyDelete
  6. public boolean strCopies(String str, String sub, int n) {
    return (str.indexOf(sub) == -1 && n == 0)
    || str.indexOf(sub) != -1
    && strCopies(str.substring(str.indexOf(sub) + 1), sub, n - 1);
    }

    ReplyDelete
  7. public boolean strCopies(String str, String sub, int n) {
    return (!str.contains(sub) && n == 0)
    || str.contains(sub)
    && strCopies(str.substring(str.indexOf(sub) + 1), sub, n - 1);
    }

    ReplyDelete
  8. public boolean strCopies(String str, String sub, int n) {
    if(str.length() < sub.length()) return n == 0;
    return str.startsWith(sub) ?
    strCopies(str.substring(1), sub, n - 1) :
    strCopies(str.substring(1), sub, n);
    }

    ReplyDelete

Follow Me

If you like our content, feel free to follow me to stay updated.

Subscribe

Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?

Upload

Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact