Java递归实现回文字符串判断返回错误布尔值问题排查

实现思路 #

我计划实现字符串回文判断功能，整体流程是先把String转成CharArray，移除所有特殊字符完成数据预处理，再做回文校验。
校验逻辑：如果字符数组首尾元素不匹配，直接终止返回false；如果匹配，就删除索引0和末尾索引的元素，递归调用方法继续判断。

问题现象 #

跑测试用例的时候，除了第一个用例结果不对，其余都符合预期，找不到错误原因，各用例运行情况：

• palin("Odsadao")：实际返回TRUE，预期返回FALSE
• palin("Acce")：实际返回FALSE，预期返回FALSE
• palin("civic")：实际返回TRUE，预期返回TRUE
• palin("Malaalam")：实际返回TRUE，预期返回TRUE
• palin("Flee to me, remote elf.")：实际返回TRUE，预期返回TRUE
• palin("Genius, this is awesome!")：实际返回FALSE，预期返回FALSE

现有代码 #

public static boolean palin(String text){
    
     char[] words = text.toCharArray(); 
     int wordlength = text.length();

     if (words[0] != words[wordlength-1])
     {
        return false;
     }
    
     else 
     { 
        if (wordlength <= 2) 
        {
          return true;
        }
    
        else {
          text = text.substring(1,text.length()-1); // Delete index 0 & n
          palin(text); //recursion with substring 
          }
      }
            
     return true;
  }

调试输出 #

加打印调试的时候，首尾字符比对的打印看起来正常，但最终结果还是错的，打印信息如下：

println(text) ==> Odsadao
println(words[0] + "" words[length-1] ==> O & O
println(text) == >DSADA
println(words[0] + "" words[length-1] ==> D & A
Palindrom? true

问题根因 #

两个核心问题：

1. 递归调用没有接收返回值：你在else分支里调用了palin(text)，但是前面没加return。内层递归跑到DSADA这一层的时候，判断出首字符D和尾字符A不相等，返回了false，但外层调用根本没接这个返回值，直接顺着逻辑走到方法最后一行return true，所以最终输出了错误的true。
2. 预处理逻辑没落地，且缺大小写统一：你最开始说要移除特殊字符、做预处理，但实际代码里根本没写这部分，也没有把字符串统一转成大写/小写再比对。第一个用例Odsadao首字母是大写O，尾字母是小写o，直接字符比对会被判定为相等，这也是第一个用例出错的原因之一。那些带标点的用例能跑对纯属于巧合。

修复参考 #

把递归的返回值补上，加上缺失的预处理逻辑就行，修复后的代码：

public static boolean palin(String text){
     // 预处理：统一转小写，移除所有非字母字符
     text = text.toLowerCase().replaceAll("[^a-z]", "");
     int wordlength = text.length();
     // 边界：长度小于等于1时一定是回文
     if (wordlength <= 1) {
         return true;
     }
     if (text.charAt(0) != text.charAt(wordlength-1)) {
        return false;
     }
     // 递归结果必须return回上层
     return palin(text.substring(1, wordlength-1));
}

内容的提问来源于stack exchange，提问作者user18906827