遞歸檢查迴文

Question

我有一個類來檢查字符串是否是迴文。我有兩個問題。

1）這是檢查迴文的最有效方法嗎？ 2）這可以遞歸地實現嗎？

public class Words { 

    public static boolean isPalindrome(String word) { 
    String pal = null; 
    word = word.replace(" ", ""); 
    pal = new StringBuffer(word).reverse().toString(); 
    if (word.compareTo(pal) == 0) { 
     return true; 
    } else { 
     return false; 
    } 

    } 

} 

有一個測試類來測試這個...懷疑它的必要的，但在這裏它是反正如果有人關心試試它能夠幫助我與任何上述兩個問題...

public class testWords { 

    public static void main(String[] args) { 
    if (Words.isPalindrome("a") == true) { 
     System.out.println("true"); 
    } else { 
     System.out.println("false"); 
    } 
    if (Words.isPalindrome("cat") == true) { 
     System.out.println("true"); 
    } else { 
     System.out.println("false"); 
    } 
    if (Words.isPalindrome("w o w") == true) { 
     System.out.println("true"); 
    } else { 
     System.out.println("false"); 
    } 
    if (Words.isPalindrome(" a ") == true) { 
     System.out.println("true"); 
    } else { 
     System.out.println("false"); 
    } 
    if (Words.isPalindrome("mom!") == true) { 
     System.out.println("true"); 
    } else { 
     System.out.println("false"); 
    } 

    } 

} 

在此先感謝您的幫助和或輸入:)

Answer 1

要實現一個「迴文檢查」遞歸，你必須在第一，最後一個字符是相同的比較。如果它們不一樣，那麼字符串肯定不是迴文。如果它們相同，則字符串可能是迴文，您需要將第二個字符與第二個到最後一個字符進行比較，依此類推，直到您的字符串中只有少於2個字符被檢查。

遞歸算法是這樣的：

public static boolean isPalindrome(String word) { 
    //Strip out non-alphanumeric characters from string 
    String cleanWord = word.replaceAll("[^a-zA-Z0-9]",""); 
    //Check for palindrome quality recursively 
    return checkPalindrome(cleanWord); 
} 
private static boolean checkPalindrome(String word) { 
    if(word.length() < 2) { return true; } 
    char first = word.charAt(0); 
    char last = word.charAt(word.length()-1); 
    if( first != last ) { return false; } 
    else { return checkPalindrome(word.substring(1,word.length()-1)); } 
} 

• 注意，我遞歸方法是不是最有效的方法，但 簡單易懂

• Marimuthu Madasamy有更有效的遞歸方法，但很難明白

• Joe F已經上市的同等有效迭代方法
  這是實現最好方法，因爲它不會引起stack overflow錯誤

Answer 2

它實際上足以只檢查到中間字符以確認它是迴文，這意味着您可以將其簡化爲如下所示：

// Length of my string. 
int length = myString.length(); 

// Loop over first half of string and match with opposite character. 
for (int i = 0; i <= length/2; i++) { 
    // If we find one that doesn't match then return false. 
    if (myString.charAt(i) != myString.charAt(length - 1 - i)) return false; 
} 

// They all match, so we have found a palindrome! 
return true; 

遞歸解決方案是非常有可能的，但它不會給你帶來任何性能上的好處（並且可能不可讀）。

Answer 3

這是可以實現遞歸嗎？

YES
這裏是例如：

public static boolean palindrome(String str) 
{ 
    if (str.length()==1 || str.length == 0) 
    return true; 
    char c1 = str.charAt(0); 
    char c2 = str.charAt(str.length() - 1); 
    if (str.length() == 2) 
    { 
     if (c1 == c2) 
     return true; 
     else 
     return false; 
    } 
    if (c1 == c2) 
    return palindrome(str.substring(1,str.length() - 1)); 
    else 
    return false; 
} 

Answer 4

這裏是另一個遞歸溶液，但使用陣列，其可以給你超過在遞歸調用字符串一些性能優點（避免substring或charAt）。

private static boolean isPalindrome(final char[] chars, final int from, 
     final int to) { 
    if (from > to) return true; 
    return chars[from] != chars[to] ? false 
            : isPalindrome(chars, from + 1, to - 1); 
} 

public static boolean isPalindrome(final String s) { 
    return isPalindrome(s.toCharArray(), 0, s.length() - 1); 
} 

的想法是，我們跟蹤陣列中的兩個位置，一個在開頭，另一個在年底，我們不斷走向中心的位置。

當位置重疊並通過時，我們完成了比較所有字符和目前爲止所匹配的所有字符;字符串是迴文。

在每次通過時，我們比較字符，如果它們不匹配，則字符串不是迴文，否則將位置移近。

Answer 5

我的兩分錢。看到人們解決問題的不同方式總是令人高興的。當然，這不是最有效的算法內存或速度方面。

public static boolean isPalindrome(String s) { 

    if (s.length() <= 1) { // got to the middle, no need for more checks 
     return true; 
    } 

    char l = s.charAt(0); // first char 
    char r = s.charAt(s.length() - 1); // last char 

    if (l == r) { // same char? keep checking 
     String sub = s.substring(1, s.length() - 1); 
     return isPalindrome(sub); 
    } 

    return false; 
}