如何用递归提取字符串中两个指定字符之间的子串

本文介绍一种基于递归的字符串处理方法，用于精确提取给定字符串中首次出现的起始字符与后续首次出现的结束字符之间的内容（不含起始和结束字符本身），并提供健壮、可运行的 java 实现及关键注意事项。

在实际开发中，有时需要从字符串中动态截取“介于某起点与某终点之间”的子串，例如从 "javascript" 中提取 'v' 到 'i' 之间的 "ascr"。这类需求看似简单，但若要求纯递归实现、不使用循环或额外辅助方法（如 indexOf），则需谨慎设计递归逻辑——尤其要避免越界、死递归和语义混淆。

下面是一个经过修正与优化的递归解法，其核心思想是：逐步收缩字符串边界，直到首字符等于 start 且尾字符等于 end，此时中间部分即为目标结果：

public static String getMiddle(String s, char start, char end) {
    // 边界检查：空串或长度不足2，无法包含“start + 中间 + end”
    if (s == null || s.length() < 2) {
        return "";
    }

    int len = s.length();
    char first = s.charAt(0);
    char last = s.charAt(len - 1);

    // 情况1：首字符不是 start → 去掉首字符，继续递归
    if (first != start) {
        return getMiddle(s.substring(1), start, end);
    }

    // 情况2：尾字符不是 end → 去掉尾字符，继续递归
    if (last != end) {
        return getMiddle(s.substring(0, len - 1), start, end);
    }

    // 情况3：首为 start 且尾为 end → 返回中间子串（不含两端）
    return s.substring(1, len - 1);
}

✅ 正确性说明：

• 该实现严格遵循“首次匹配起点、首次匹配终点”的语义：先定位最左 start（通过不断裁剪前缀），再确保在该 start 右侧找到第一个 end（通过不断裁剪后缀）。
• 例如输入 "javascript"、start='v'、end='i'：
  • "javascript" → 首 'j'≠'v' → "avascript"
  • "avascript" → 首 'a'≠'v' → "script"
  • "script" → 首 's'≠'v' → "cript"
  • "cript" → 首 'c'≠'v' → "ript"
  • "ript" → 首 'r'≠'v' → "ipt"
  • "ipt" → 首 'i'≠'v' → "pt"
  • "pt" → 首 'p'≠'v' → "t" → 长度 → 显然上述路径不对——问题在于原始示例 "javascript" 中 'v' 在索引 2，'i' 在索引 5，但 'v' 后第一个 'i' 实际是 'i'（索引 5），中间为 "ascr"（索引 3–6？需校验）。

⚠️ 重要澄清与改进：
原题示例 "javascript" 中 'v'（索引 2）到 'i'（索引 5）之间的子串应为 s.substring(3, 5) = "sc"？但期望输出是 "ascr" —— 这说明题目隐含语义是：从 start 第一次出现位置开始，到 end 在其之后第一次出现的位置结束，返回二者之间的全部字符（不含 start 和 end）。即：

• startIdx = s.indexOf(start)
• endIdx = s.indexOf(end, startIdx + 1)
• 结果 = s.substring(startIdx + 1, endIdx)

而纯递归模拟 indexOf 需要双指针式递归（记录当前搜索位置）。更鲁棒的递归实现如下：

public static String getMiddle(String s, char start, char end) {
    return getMiddleHelper(s, start, end, 0);
}

private static String getMiddleHelper(String s, char start, char end, int pos) {
    if (pos >= s.length()) return "";

    // 找到 start
    if (s.charAt(pos) == start) {
        int endPos = findEndAfter(s, end, pos + 1);
        if (endPos != -1) {
            return s.substring(pos + 1, endPos);
        }
        return 
""; // 找不到 end
    }
    return getMiddleHelper(s, start, end, pos + 1);
}

private static int findEndAfter(String s, char end, int from) {
    if (from >= s.length()) return -1;
    if (s.charAt(from) == end) return from;
    return findEndAfter(s, end, from + 1);
}

? 关键注意事项：

• 原始尝试中存在未声明变量 str、重复调用无返回值、逻辑分支缺失等问题，易导致 StringIndexOutOfBoundsException 或无限递归；
• 必须添加空值/长度校验，否则递归基线失效；
• 若 start 与 end 不存在、start 在 end 右侧、或 end 不存在于 start 之后，应返回空字符串而非抛异常；
• 时间复杂度为 O(n)，空间复杂度为 O(n)（递归栈深度）。

综上，递归提取子串的关键在于明确语义、设置安全基线、分治收缩，并优先保证逻辑完整性而非代码行数精简。