符合特定规则的ab字符串递归校验代码问题排查——aba、abababa等用例校验失效原因分析

Great question! Let's walk through the bugs in your recursive checkAB function and fix them so it correctly validates all cases per your rules.

First, let's break down the key issues in your current code that cause failures for cases like aba or abababa:

Key Problems in the Original Implementation #

• Missing return values for recursive calls: When you call checkAB(input, start+1, end) or checkAB(input, start+3, end), you don't return the result of these recursive calls. This leads to undefined behavior—your function will fall through to the end without returning a valid bool value, resulting in random true/false outputs.
• Unchecked out-of-bounds memory access: You access input[start+1] and input[start+2] without verifying if those indices are within the string's bounds. For example, if the string is just "a", start+1 will point past the null terminator, causing invalid memory reads.
• No handling for 'a' followed by empty string: Rule (b) allows an 'a' to be the last character, but your code doesn't explicitly check for this scenario. When the current 'a' is the final character, the function should return true.

Corrected Code with Explanations #

Here's the fixed implementation, with comments highlighting each change:

#include <stdbool.h> // Ensure bool type is properly defined

int length(char input[]) {
    int count = 0;
    for (int i = 0; input[i] != '\0'; i++) {
        count++;
    }
    return count;
}

bool checkAB(char input[], int start, int end) {
    // Base case: we've successfully traversed the entire string
    if (start == end) {
        return true;
    }

    // Fail immediately if current character isn't 'a' (violates rule a/b)
    if (input[start] != 'a') {
        return false;
    }

    // Case 1: 'a' is followed by another 'a' (check bounds first!)
    if (start + 1 < end && input[start+1] == 'a') {
        return checkAB(input, start + 1, end);
    }

    // Case 2: 'a' is followed by "bb" (ensure we don't go out of bounds)
    if (start + 2 < end && input[start+1] == 'b' && input[start+2] == 'b') {
        // Recurse from after the "bb" (rule c allows empty or 'a' next)
        return checkAB(input, start + 3, end);
    }

    // Case 3: 'a' is the last character (allowed by rule b)
    if (start + 1 == end) {
        return true;
    }

    // If none of the valid cases match, the string is invalid
    return false;
}

bool checkAB(char input[]) {
    int len = length(input);
    // Empty string is invalid (must start with 'a' per rule a)
    if (len == 0) {
        return false;
    }
    return checkAB(input, 0, len);
}

What We Fixed #

1. Added return statements for recursive calls: Now each recursive branch returns its result, ensuring the validation outcome propagates correctly up the call stack.
2. Added bounds checking: We verify start+1 < end or start+2 < end before accessing those indices, preventing invalid memory reads.
3. Explicit empty string after 'a' handling: The final if (start+1 == end) checks if the current 'a' is the last character, which is permitted by rule (b).
4. Empty string edge case: The top-level function now returns false for empty strings, since rule (a) requires the string to start with 'a'.

Test Case Validation #

Let's confirm with your problematic cases:

• aba: The first 'a' is followed by a single 'b' (not another 'a' or "bb"), so the function returns false (correct, as this violates rule (b)).
• abababa: The first 'a' is followed by a single 'b', which doesn't meet any valid criteria, so returns false (correct).
• Valid cases like "a", "aa", "abb", "abba", "aabb" will all return true as expected.

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