时间戳

首页 > 解决方案 > CS50 面试问题 - 查找最长的子串递归之谜 - 为什么测试用例 #4 不起作用？

python - CS50 面试问题 - 查找最长的子串递归之谜 - 为什么测试用例 #4 不起作用？

问题描述

问题：

给定一个字符串，找出最长的不重复字符的子串的长度。例如，在字符串“abcabcbb”中，没有重复字符的最长子串的长度为 3（“abc”等）。

问题描述：

嗨，我为此使用了 Python 和递归解决方案。除了 TC4，每个测试用例都按预期工作，我不知道为什么。看起来当找到最终的子字符串（“wekf”）时，它会停留在同一个迭代中并再次以原始（！）字符串开始。它怎么还能保留原来的字符串？输出是完全出乎意料的“pwekf”......请帮助我解决这个大谜团。

代码：

def find_longest_substring(string, longest=0):
    current_longest_string = ""
    
    for char, i in zip(string, range(len(string))):
        if char not in current_longest_string:
            current_longest_string = f'{current_longest_string}{char}'
        # if character is already in current_longest_string, count len() and 
        # start looking again from last spot
        else:
            longest = len(current_longest_string) \
                if len(current_longest_string) > longest else longest
            find_longest_substring(string[i:], longest)

    longest = len(current_longest_string)
    return longest, current_longest_string


# TC1
print(find_longest_substring("abcabcbb"))
# TC2
print(find_longest_substring("bbbbb"))
# TC3
print(find_longest_substring("abcdef"))
# TC4
print(find_longest_substring("pwwekf"))
# TC5
print(find_longest_substring(""))

固定的：

def find_longest_substring(string, longest=0):
    current_longest_string = ""

    for char, i in zip(string, range(len(string))):
        if char not in current_longest_string:
            current_longest_string = f'{current_longest_string}{char}'
        # if character is already in current_longest_string, count len() and
        # start looking again from last spot
        else:
            longest = len(current_longest_string) \
                if len(current_longest_string) > longest else longest
            longest_new = find_longest_substring(string[i:], longest)
            if longest_new > longest:
                return longest_new

    longest = len(current_longest_string)
    return longest

输出：

(3, 'abc')
(1, 'b')
(6, 'abcdef')
(5, 'pwekf')
(0, '')

标签： pythonrecursioncs50

解决方案

您可能会注意到这是唯一一个从一开始就没有正确结果的测试用例。您可能还会注意到您的函数是贪婪的，并且永远无法退出错误的解决方案。递归什么都不做，递归调用的输出在任何地方都没有使用。

在 else 路径中，您必须：

  • 进行递归调用
  • 检查解决方案是否比您当前的解决方案更好
  • 如果是，更换它
  • 跳出 for 循环

推荐阅读