java - 包含“bab”的 boolean 函数

我怎么有一个递归的布尔方法，将检查它是否包含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;
    }

最佳答案

递归应视为两个部分。

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

2）递归的情况。
这样可以将问题分解为更细小的问题，并且如果将它们分解得足够多，则可以有一个基本案例。

@Logiraptro有一个简单的递归示例。

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是字符串的长度。对于大多数长度来说，这都不是什么大问题，但是如果您搜索长度为一百万的字符串，则可能意义重大。在第一个版本中，我们的堆栈深度约为1,000,000！但是有了这个二进制版本，我们只需要深入14个级别即可。

但是，这是有代价的，因为我们的解决方案涉及更多。

我们的基本情况
1）如果字符串小于搜索字符串的长度，则返回false。
2）如果字符串是搜索字符串的长度，则等于true，否则返回false。
3）如果字符串出现在字符串的中点上方，则返回true。

如果所有这些都不成立，我们将字符串分成两部分，然后递归检查该字符串。

这是该算法的一个示例，您可以将“ 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;
}