包含“bab”的布尔函数

Question

我怎么可能有一个递归布尔方法来检查它是否包含BAB。我有这个，但我想做它递归。

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

Answer 1

递归应该被认为是两个部分。

1）一个基本情况。这是一个很简单的情况，很容易确定。到目前为止，这是一个基本情况的良好开端。1）字符串是否小于3？然后返回false。2）字符串是否以“bab”开头，然后返回true。

2）一个递归案例。这将问题分解成一个更小的问题，如果你把它们分解得足够多，你就有了一个基本案例。

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

这将使用基本案例，并作为递归案例检查从索引1开始的字符串。这只减少了我们的字符串一个宪章，但足以解决问题。

这意味着我们最终得到字符串长度的堆栈级别。

我们能做得更好吗？一点，通过将问题分解一半，我们只需要一个ln(n)的堆栈级别，其中n是字符串的长度。对于大多数长度来说，这并不是一个大问题，但是如果您搜索的字符串长度为100万，那么它可能很重要。与第一个版本，我们的堆栈将是大约100万深！但是对于这个二进制版本，我们只需要深入到大约14层。

这里是这个算法的一个例子，你可以用你喜欢的任何字符串替换“bab”，尽管它还没有经过充分的测试，我很肯定它会好的。

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