Java递归练习问题：移除字符串指定字符数组元素仅删除单个字符

我们正在课堂上练习递归，有一道题难住了我（要求不得使用循环）：需要写一个方法，接收一个String和一个char数组，返回移除了该数组中所有字符后的字符串。

目前我的代码只能移除单个字符，比如输入：

char[] remLetArray = {'a', 's'};
System.out.println(removeLetters("asdfghsassaaaae", remLetArray));

返回结果是sdfghssse，但正确结果应该是dfghe。我的完整代码如下：

// helper method
public static String removeLetters(String str, char[] ch, int pointer) {
    if (pointer != ch[ch.length - 1]) {
        if (str.length() == 0) {
            return removeLetters(str, ch, pointer + 1);
        }

        if (str.charAt(0) == ch[pointer]) {
            return removeLetters(str.substring(1), ch);
        } else {
            return str.charAt(0) + removeLetters(str.substring(1), ch);
        }

    } else {
        System.out.println(str);
        if (str.length() == 0) {
            return "";
        }

        if (str.charAt(0) == ch[pointer]) {
            return removeLetters(str.substring(1), ch);
        } else {
            return str.charAt(0) + removeLetters(str.substring(1), ch);
        }
    }
}

// actual method
public static String removeLetters(String str, char[] ch) {
    return removeLetters(str, ch, 0);
}

问题分析 #

你的代码有两个致命逻辑错误：

1. 指针判断完全错误：你用pointer != ch[ch.length - 1]把指针索引和数组最后一个字符的值做比较，这完全不符合逻辑——应该判断指针索引是否还没遍历完数组，比如pointer < ch.length。
2. 递归调用漏传指针参数：处理字符时调用removeLetters(str.substring(1), ch)，没有传递当前的pointer，导致触发无指针的重载方法，重新从pointer=0开始遍历，逻辑彻底混乱。

修正方案 #

这里提供两种递归思路的实现，都符合无循环要求：

思路1：逐个移除数组中的字符（先清完一个字符再处理下一个）

// 辅助方法：移除字符串中指定的单个字符
private static String removeSingleChar(String str, char c) {
    if (str.isEmpty()) {
        return "";
    }
    return str.charAt(0) == c 
        ? removeSingleChar(str.substring(1), c) 
        : str.charAt(0) + removeSingleChar(str.substring(1), c);
}

// 主方法：遍历字符数组，递归移除每个目标字符
public static String removeLetters(String str, char[] ch) {
    if (ch.length == 0) {
        return str;
    }
    // 先移除第一个目标字符，再递归处理剩余的字符数组
    String afterFirstRemove = removeSingleChar(str, ch[0]);
    char[] remainingChars = new char[ch.length - 1];
    System.arraycopy(ch, 1, remainingChars, 0, remainingChars.length);
    return removeLetters(afterFirstRemove, remainingChars);
}

思路2：单递归判断字符是否需要移除（一次递归处理所有目标字符）

// 辅助方法：判断当前字符是否属于要移除的数组
private static boolean shouldRemove(char c, char[] ch) {
    if (ch.length == 0) {
        return false;
    }
    if (c == ch[0]) {
        return true;
    }
    char[] remainingChars = new char[ch.length - 1];
    System.arraycopy(ch, 1, remainingChars, 0, remainingChars.length);
    return shouldRemove(c, remainingChars);
}

// 主递归方法：逐个处理字符串字符
public static String removeLetters(String str, char[] ch) {
    if (str.isEmpty()) {
        return "";
    }
    char firstChar = str.charAt(0);
    return shouldRemove(firstChar, ch)
        ? removeLetters(str.substring(1), ch)
        : firstChar + removeLetters(str.substring(1), ch);
}

测试你的输入，两种方法都会返回dfghe，符合预期。

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