在Python递归时出现神秘输出。

huangapple go评论65阅读模式
英文:

Mysterious output while recursing in python

问题

你的算法在处理字符串时似乎有一些问题,导致了出现了意外的结果。在这段代码中,你似乎尝试着找出最长连续不重复字符子串的长度。但是,在处理字符串时,有些部分可能会出现混乱。

在你的代码中,having 列表用于存储已经遇到的字符,但在递归调用时,你没有清空这个列表,导致了问题。

当你得到了 DONE 5 后,你应该清空 having 列表,以便在处理新的子串时重新开始记录不重复的字符。否则,having 列表会继续包含之前的字符,这可能导致不正确的结果。

为了解决这个问题,你可以在每次递归调用之前,在 getmax(new_s) 之前,添加一行 having = [],以清空 having 列表,使其只包含新的子串中的字符。

这应该有助于你更好地理解代码中发生的问题,而不会完全揭示解决方案。

英文:

I'm kinda new here and I just know the meaning of a recursion function but something strange happens when I try to excute it.

I'm trying to solve a leetcode problem of "Longest Substring Without Repeating Characters". In short they want to output the length of the longest continous substring in a provided string without any repeating charachters.

Here's my code

def getmax(s):
    having = []
    length = 0
    highest = [0]
    
    for i in  s:
        if i not in having:

            length +=1
            having.append(i)
            
            print(having)
            
            highest.append(length)
            
            print(length)


            if s.index(i) == len(s)-1:
                print("DONE",max(highest))
                return max(highest)
   
        else:
            new_s = s[s.index(i)+1:]
            getmax(new_s)

            
print(getmax("ckilbkd"))

So, my algorithm for this is to start incrementng the length, adding the length to a list to find the maximum later on, untill finding a repeated character. If this happens, the function is called again with a new string such that if for example s = dvdf the new_s string is only vdf. and if s = ckilbkd , new_s will be ilbkd. I can't explain it clearly but it removes anything before the original repeated character.

After that i run the function again on the new shorter string till finding a repated charachter. If not and the new_s is finally all unique i want to return the maximum value of the list that i have been appending the lengths in so far. And to know that the string is finished I added the condition if s.index(i) == len(s)-1:to see if it's the last charachter in the string or not.

For the string "ckilbkd" output should be 5 "ilbkd". During my debugging process I found this:

['c'] 
1                          #starts with the c, length is now 1
['c', 'k']
2                          #unrepeated charcter length is 2 
['c', 'k', 'i']
3                          #unrepeated charcter length is 3
['c', 'k', 'i', 'l']
4                           #unrepeated charcter length is 4
['c', 'k', 'i', 'l', 'b']
5                           #unrepeated charcter length is 5
['i']
1                           #repeated charachter found, starts over with new_s = ilbkd, length is now 1
['i', 'l']
2                           #unrepeated charcter length is 2 
['i', 'l', 'b']
3                           #unrepeated charcter length is 3 
['i', 'l', 'b', 'k']
4                           #unrepeated charcter length is 4 
['i', 'l', 'b', 'k', 'd']
5                           #unrepeated charcter length is 5
DONE 5                      #Should stop HERE
['c', 'k', 'i', 'l', 'b', 'd']
6                           #Dont understand what's happening here
DONE 6
6

It's working fine till the line after DONE 5.
then the list having is now a mess that i can't understand at all.

I'm trying to understand why is this happening more than to actually solve the problem, would appreciate if someone could explain what's happening without actually spoiling the solution.

答案1

得分: 1

你在递归情况中忘记了return。所以,对getmax(new_s)的调用获取了基本情况的返回值,即max(highest),但它没有处理它。然后for循环继续...

为什么函数返回了截断版本的整个字符串?

原因很简单:因为在else块中没有return(或break),所以for循环没有被中断,继续向having添加字母。然而,触发else块执行的重复字母没有被添加。

基本上,你的函数看到了'c' -> 'c'不在having中 -> 将'c'添加到having中。
'k' -> 'k'不在having中 -> 将'k'添加到having中... 如此往复,直到遇到第二个'k'
第二个'k' having中 -> 不添加它,调用getmax,但它不重要,因为它对该调用的输出没有做任何操作。所以它继续循环,现在它看到'd',它不在having中,并将其附加。最后,你得到了整个字符串,除了没有附加第二个'k'

英文:

You forgot the return in the recursive case. So, the call to getmax(new_s) get's the return of the base case, max(highest), but it doesn't do anything about it. And the for loop continues...


Why does the function returns a truncated version of the whole string?

The reason is simple: Because you don't have a return (or a break) in the else block, the for loop is not broken and keeps adding letters to having. However, the repeated letter that triggered the execution of the else block is not added.

Basically, your functions sees 'c' -> 'c' is not in having -> appends 'c' to having.
'k' -> 'k' is not in having -> appends 'k' to having ... and so on until it reaches the second 'k'.
Second 'k' is in having -> doesn't append it, calls getmax with new_s, but it doesn't matter because it does nothing with the output of that call. So it keeps looping and now it sees 'd', which is not in having, and appends it. At the end you get the whole string except for the second 'k' that wasn't appended.

huangapple
  • 本文由 发表于 2023年6月1日 13:35:17
  • 转载请务必保留本文链接:https://go.coder-hub.com/76378919.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定