布爾函數，其中包含「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）遞歸案例。 這會將問題分解爲更加麻煩的問題，如果您將它們分開，希望您有一個基本案例。

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

這使用您的基本情況，並作爲一個遞歸的情況下檢查從索引一個字符串。這隻會減少我們的字符串一個章程，但足以解決問題。

這意味着我們結束了字符串長度的堆棧級別。

我們可以做得更好嗎？有一點，通過將問題分解成一半我們只需要一個ln（n）的堆棧級別，其中n是字符串的長度。這對於大多數長度來說並不是什麼大問題，但是如果你正在搜索一個長度爲一百萬的字符串，它可能很重要。有了第一個版本，我們的堆棧將會有大約100萬個！但對於這個二進制版本，我們只需要深入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; 
} 

Answer 2

無需遞歸;）你正在尋找String.contains

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

Answer 3

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

但是，你真的應該使用String.contains