java 中检测回文的递归方法

Question

我正在尝试追踪检测单词是否为回文的递归方法：

public static boolean isPalindrome(String word) {
    if (word.length() == 0 || word.length() == 1) {
        return true; 
    } else if (word.charAt(0) == word.charAt(word.length() - 1)) {
        return isPalindrome(word.substring(1, word.length() - 1)); 
    } else {
        return false;
    } 
}

我用过的词是："abba"。该方法的第一个实例采用 else 方式，因为第一个 if 条件的评估，所以它评估 if else 语句中的条件得到一个 true 作为结果，然后该方法 returns 运行带有单词 "bb" 的方法。递归再次运行该方法："bb"的长度不为0或1，则走else方式，判断第一个'b'是否等于第二个'b'，是是的，所以 returns 再次使用相同方法的运行，但现在子字符串开始于位置 1 的字符 (beginIndex) 'b' 并结束于位置 0 的字符 ( endIndex），但是 beginIndex 大于 endIndex，这应该会抛出 IndexOutOfBoundsException ... 但是该方法有效。有人可以向我解释一下吗？谢谢

Answer 1

在您的第二次迭代中，单词是 bb。这意味着长度是 2.

你的子字符串是 word.substring(1, 1)。因此它不会（并且正确地）抛出异常，而是 return 一个空字符串。

Answer 2

添加一些println可以帮助你调试，检查here。

public static boolean isPalindrome(String word){
    System.out.println("Checking "+word+" length: "+word.length());
    if(word.length()==0 || word.length()==1){
        System.out.println("Base Case");
        return true; 
    } else if(word.charAt(0)==word.charAt(word.length()-1)){
        System.out.println("Resursive case substring(1,"+(word.length()-1)+")");
        return isPalindrome(word.substring(1, word.length()-1)); 
    }else {
        return false;
    } 
}

Checking abba length: 4
Resursive case substring(1,3)
Checking bb length: 2
Resursive case substring(1,1)
Checking  length: 0
Base Case

正如您在第二次递归调用中看到的那样，您有 "bb" 并且您将要检查 substring(1,1)，文档说明：

IndexOutOfBoundsException - if the beginIndex is negative, or endIndex is larger than the length of this String object, or beginIndex is larger than endIndex.

beginIndex 不大于 endIndex 所以不会抛出异常。您可以通过解释

来表示子字符串在索引 1 处的字符之后开始并在索引 0 处的字符之后结束

Returns a new string that is a substring of this string. The substring begins at the specified beginIndex and extends to the character at index endIndex - 1. Thus the length of the substring is endIndex-beginIndex.

|      b       |       b      |
                ^
                beginIndex (starts at 1)
              ^
              endIndex - 1 (ends past 0)

java 中检测回文的递归方法

Recursive method in java to detect a palindrome

java

recursion

palindrome