Самая длинная подстрока без повторяющихся символов »Рекурсивное решение Leetcode не работает - PullRequest
Новая
       3

Самая длинная подстрока без повторяющихся символов »Рекурсивное решение Leetcode не работает

1 голос
/ 01 февраля 2020

Получает принятый для всех тестовых случаев, если введенная строка не является слишком длинной. Почему это происходит, и могу ли я сделать это решение рекурсивно? Это потому, что 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)

1 Ответ

0 голосов
/ 01 февраля 2020

Этот код решает эту проблему в линейном времени, объяснение в 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))
...