没有重复字符的最长子字符串" Leetcode 递归解决方案不起作用

Question

被所有测试用例接受，除非输入的字符串太长。为什么会发生这种情况，我可以递归地制作此解决方案吗？这是因为python作为一种语言有递归限制(这在java中可以工作吗？(还是有其他问题？

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0:
return 0
if len(s) == 1:
return 1
start = 0
index = 0
length = len(s)
list = []
strr = ""
listt = self.getSubstring(s,[],index,list,start,length)
for i in listt:
if len(i) > len(strr):
strr = i
print(len(strr))
return len(strr)

def getSubstring(self,s,keys,index,list,start,length):
#print("s",s)
#print("start",start)
#print("index",index)
#print("keys",keys)
#print("list",list)
if index == len(s)-1:
if s[index] in keys:
list.append(s[start:index])
#print(list)
return list
else:
list.append(s[start:index+1])
#print(list)
return list
if s[index] in keys:
list.append(s[start:index])
return self.getSubstring(s,[],start+1,list,start+1,length)
else:
keys.append(s[index])
return self.getSubstring(s,keys,index+1,list,start,length)

Answer 1

这段代码以线性时间解决了这个问题，解释在 https://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/或者你可以签出大致相同的 https://www.geeksforgeeks.org/print-longest-substring-without-repeating-characters/：

NO_OF_CHARS = 256
def longestUniqueSubsttr(string): 
n = len(string) 
cur_len = 1        # To store the length of current substring 
max_len = 1        # To store the result 
prev_index = 0    # To store the previous index 
i = 0
# Initialize the visited array as -1, -1 is used to indicate 
# that character has not been visited yet. 
visited = [-1] * NO_OF_CHARS 
# Mark first character as visited by storing the index of 
# first character in visited array. 
visited[ord(string[0])] = 0
# Start from the second character. First character is already 
# processed (cur_len and max_len are initialized as 1, and 
# visited[str[0]] is set 
for i in xrange(1, n): 
prev_index = visited[ord(string[i])] 
# If the currentt character is not present in the already 
# processed substring or it is not part of the current NRCS, 
# then do cur_len++ 
if prev_index == -1 or (i - cur_len > prev_index): 
cur_len+= 1
# If the current character is present in currently considered 
# NRCS, then update NRCS to start from the next character of 
# previous instance. 
else: 
# Also, when we are changing the NRCS, we should also 
# check whether length of the previous NRCS was greater 
# than max_len or not. 
if cur_len > max_len: 
max_len = cur_len 
cur_len = i - prev_index 
# update the index of current character 
visited[ord(string[i])] = i 
# Compare the length of last NRCS with max_len and update 
# max_len if needed 
if cur_len > max_len: 
max_len = cur_len 
return max_len 
# Driver program to test the above function 
string = "ABDEFGABEF"
print "The input string is " + string 
length = longestUniqueSubsttr(string) 
print ("The length of the longest non-repeating character" +
" substring is " + str(length)) 

Answer 2

递归实现在伪代码中是这样的：

function lengthOfLongestSubstring(s)
for each c in s
unique[c] = false
n = s.length()
max_len = 0
for i in range(0, n):
max_len = max(max_len, max_sub_str(s, i)
return max_len
function max_sub_str(s, i)
if (i >= s.length() || unique[s[i]]) return 0;
unique[s[i]] = 1;
int count = 1 + max_sub_str(s, i + 1);
unique[s[i]] = 0;

return count;