递归函数为何遗漏字符？Python最长有序子串代码问题排查

测试用例 s='azcbobobegghakl' 的预期最长字母有序子串应为 "beggh"，但递归代码运行后仅输出 "begg"，遗漏了字符h。

需求说明 #

假设s为小写字符串，编写程序输出s中字母按字母顺序排列的最长子串；若存在多个最长子串，输出第一个（如s='abcbcd'时应输出"abc"）。

我的代码 #

s = "azcbobobegghakl"
current_string = ''
longest_string = ''
n = 0


def sorting_string(n):
    global current_string
    global longest_string
    if n == (len(s) - 1):  
        return 0
    elif ord(s[n]) <= ord(s[n+1]):
        
        
        if len(current_string) <= 1:
            current_string = current_string + s[n]
            return sorting_string(n + 1)
        
        if ord(s[n+1]) > ord(current_string[-1]):
                current_string = current_string + s[n]
        
        else:
            if ord(s[n]) >= ord(current_string[-1]):
                current_string = current_string + s[n]
            
        
            
        if len(current_string) > len(longest_string):
            longest_string = current_string
            
        else:
            current_string = ''
            
        return sorting_string(n + 1)
    
    else:
        current_string = ''

        return sorting_string(n + 1)
        

print(s)
sorting_string(n)
print(longest_string)
print(current_string)
print(ord("g"))
print(ord("h"))

实际输出 #

azcbobobegghakl
begg
ak
103
104

问题分析 #

你的代码存在几个核心逻辑错误：

1. 字符添加逻辑混乱：处理递增字符时，始终只追加s[n]而非s[n+1]，导致h这类后续字符永远无法加入当前子串。
2. 错误清空当前子串：当当前子串长度不大于最长子串时直接清空，打断了后续连续递增字符的拼接（比如begg之后的h本应延续，却被强制清空）。
3. 边界处理缺失：递归到最后一个字符时直接返回，未将其加入当前子串并与最长子串做对比，导致末尾字符遗漏。

修正后的递归代码 #

s = "azcbobobegghakl"
# 初始化：空串特殊处理，非空串则以第一个字符作为当前子串初始值
current_string = s[0] if s else ''
longest_string = current_string


def find_longest_substring(n):
    global current_string, longest_string
    # 递归终止条件：遍历完所有字符
    if n >= len(s):
        return
    # 当前字符满足递增，追加到当前子串
    if ord(s[n]) >= ord(current_string[-1]):
        current_string += s[n]
        # 仅当当前子串更长时更新最长子串，保证第一个最长子串被保留
        if len(current_string) > len(longest_string):
            longest_string = current_string
    else:
        # 不满足递增，重置当前子串为当前字符
        current_string = s[n]
    # 递归处理下一个字符
    find_longest_substring(n + 1)


find_longest_substring(1)  # 从第二个字符开始遍历，第一个字符已初始化完成
print(s)
print(longest_string)

修正后输出 #

azcbobobegghakl
beggh

修正逻辑说明 #

• 初始化合理：避免空串处理的混乱，直接以第一个字符作为当前子串的起点。
• 字符追加逻辑清晰：只要当前字符大于等于当前子串最后一个字符，就直接追加，保证所有连续递增字符都被纳入。
• 最长子串更新规则明确：仅在当前子串长度超过最长子串时更新，确保出现多个同长度子串时，第一个被保留。
• 边界处理完善：递归遍历所有字符，不会遗漏末尾字符的判断。

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