Java递归统计字符串x数量时出现数组越界错误求助

核心错误原因 #

1. 字符串索引越界 #

当递归处理到字符串只剩最后一个字符时（长度为1），代码直接调用s.charAt(1)，但字符串索引从0开始，长度为1的字符串最大索引为0，这会直接抛出StringIndexOutOfBoundsException——这就是结尾带x的测试用例报错的根本原因。

2. 重复计数逻辑错误 #

原代码处理连续"xx"时，第一个x被计为2次后，递归调用substring(1)会再次处理第二个x，导致第二个x被重复统计，最终结果偏大。

修复方案 #

方案一：修正递归逻辑 #

在访问下一个字符前先判断字符串长度，同时遇到连续xx时跳过下一个字符，避免重复统计：

public class CountXWithDubs {

    /**
     * Count the number of 'x's in the string. Any 'x' that is followed by
     * another 'x' should count double (e.g. "axxbxc" -> 4)
     * 
     * @param s a string.
     * @return the count of x's.
     */
    public static int countXWithDubs(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int count = 0;
        if (s.charAt(0) == 'x') {
            // 仅当字符串长度大于1时，才检查下一个字符
            if (s.length() > 1 && s.charAt(1) == 'x') {
                count += 2;
                // 跳过下一个x，避免重复统计
                return count + countXWithDubs(s.substring(2));
            } else {
                count += 1;
            }
        }
        // 正常递归处理下一个字符
        return count + countXWithDubs(s.substring(1));
    }

    @Test
    public void testXSEnd() {
        assertEquals("Incorrect result with x at end", 2,
                countXWithDubs("abxcdx"));
    }
    
    @Test
    public void testDoubleXEnd() {
        assertEquals("Incorrect result with double x at end", 4,
                countXWithDubs("abxcdxx"));
    }
    
    @Test
    public void testBunchOfXs() {
        assertEquals("Incorrect result with bunch of x's", 13,
                countXWithDubs("xxxaxbxxcxdxx"));
    }
}

方案二：改用迭代实现（更稳妥） #

递归容易出现索引越界和栈溢出问题，改用循环迭代更直观稳定：

public static int countXWithDubs(String s) {
    if (s == null || s.isEmpty()) {
        return 0;
    }
    int count = 0;
    int length = s.length();
    for (int i = 0; i < length; i++) {
        if (s.charAt(i) == 'x') {
            // 检查当前x后是否紧跟另一个x，且不是最后一个字符
            if (i < length - 1 && s.charAt(i + 1) == 'x') {
                count += 2;
            } else {
                count += 1;
            }
        }
    }
    return count;
}

验证结果 #

修复后的代码可以通过所有测试用例：

• testXSEnd("abxcdx")：两个独立x，各计1次，总和2
• testDoubleXEnd("abxcdxx")：独立x计1次，连续xx分别计2次和1次，总和1+2+1=4
• testBunchOfXs("xxxaxbxxcxdxx")：按规则计算总和为13，符合预期

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