CODEWITHSUNDEEP
javarecursion
Ris
Ris

Reputation: 1912

boolean function that contains "bab"

How could I have a recursive boolean method that will check if it contains bab. I have this but I I'd like to do it recursively. 

public static boolean hasBAB(String str) {
      if (str.length() < 3) return false;
      if (str.substring(0,3).equals("bab"))
        return true;
      else
        return false;
    }

Upvotes: 1

Views: 140

Answers (3)

ansible
ansible

Reputation: 3579

Recursion should be thought of as two parts.

1) A base case. This is trivial case that can easly be determined. What you have so far is a good start to a base case. 1) Is the string less then 3? Then return false. 2) Does the string start with "bab" then return true.

2) A recursive case. This splits the problem up into a tinier problems, and if you split them up enough hopefully you have a base case.

@Logiraptro has a good example of a simple recursion.

public static boolean hasBAB(String str) {
  if (str.length() < 3) return false;
  if (str.substring(0,3).equals("bab"))
    return true;
  else
    return hasBAB(str.substring(1));
}

This uses your base cases, and as a recursive case checks the string from index one on. This reduces our string only by one charter, but is enough to solve the problem.

This means we end up with a stack level of the length of the string.

Can we do better? A little, by breaking the problem in half we only need a stack level of ln(n) where n is the length of string. This is not a big deal for most lengths, but if you were searching a string with a length of one million it maybe significant. With the first version our stack would be about a 1,000,000 deep! But with this binary version we only need to go about 14 levels deep.

This comes at a cost though, our solution because more involved.

Our base cases 1) If the string is less then the length of the search string, return false. 2) If the string is length of the search string, if they are equal return true, else return false. 3) If the string appears over the mid point of the string return true.

If none of these are true,we break the string into two parts and recursively check over that string.

Here is an example of that algorithm, you can replace "bab" with any string you like, although it hasn't been fully tested for that I'm pretty sure it will be okay.

public static boolean hasBAB(String str) {
      String searchString = "bab";

      // Base cases
      if (str.length() < searchString.length()) 
          return false;

      if (str.length() == searchString.length())
      {
          if (str.equals(searchString))
          {
              return true;
          }
          return false;
      }

      int halfWay = str.length()/2;

      // Now check for the search string over the "break"
      for (int i = 0; i < searchString.length(); i++)
      {
          int startIndex = halfWay - 1 - i;
          int endIndex = startIndex + 3;
          if (startIndex >= 0)
          {
              String substring = str.substring(startIndex, endIndex);
              if (substring.equals(searchString))
              {
                  return true;
              }
          }
      }

     // Recursive Cases 
     //  We did find the search string over the break,so break the string into two equal(ish) pieces and check those 
     if(hasBAB(str.substring(0,halfWay -1)))
         return true;

     if(hasBAB(str.substring(halfWay, str.length())))
         return true;

     return false;
}

Upvotes: 2

Logiraptor
Logiraptor

Reputation: 1518

public static boolean hasBAB(String str) {
  if (str.length() < 3) return false;
  if (str.substring(0,3).equals("bab"))
    return true;
  else
    return hasBAB(str.substring(1));
}

But you should really use String.contains

Upvotes: 5

Johannes H.
Johannes H.

Reputation: 6167

No need for recursion ;) You're looking for String.contains

public static boolena hasBAB (String str) {
    if (String.length() < 3) return false;
    else return str.contains("bab");
}

Upvotes: 4

Related Questions