파이썬 챌린지: Leetcode 3. 반복되는 문자가 없는 가장 긴 하위 문자열

15738 단어 leetcodepython

의문


  • 주어진 문자열 s에서 반복되는 문자가 없는 가장 긴 하위 문자열의 길이를 찾습니다.

  • 예시


  • 예 1:

  • 입력: s = "abcabcbb"
    출력: 3
    설명: 답은 길이가 3인 "abc"입니다.
  • 예 2:

  • 입력: s = "bbbbbb"
    출력: 1
    설명: 정답은 길이가 1인 "b"입니다.
  • 예 3:

  • 입력: s = "pwwkew"
    출력: 3
    설명: 답은 길이가 3인 "wke"입니다.
    응답은 하위 문자열이어야 합니다. "pwke"는 하위 문자열이 아니라 하위 시퀀스입니다.

    제약:


  • 0 <= s.length <= 5 * 104
  • s 영문, 숫자, 기호 및 공백으로 구성됩니다.

  • 내 시도



    1회 시도(마지막 2회 실패, 제한 시간 초과)


  • 알고리즘

  • >Find the length of the longest substring without repeating characters.
    initialise the length_of_s equals to length of s
    initialise the length_list_of_sub_string to the empty string
    
    define a find_and_record_substring program:
        initialise seen_string as an empty string
        initialise seen_dictionary as an empty dictionary
        initialise the length equals to 0
        for each character in s:
           if the charcter do not found in seen_string:
               add the character to seen_string
            otherwise:
                initialise the length equals to length of seen_string
                update seen_dictionary with length as key, seen_string as value
                set seen_string to empty string
                add the character to seen_string
        return the maximum of the key of the dictionary
    
    >>find and record each substring without repeating characters in the string s
    
    repeat the find_and_record_substring program for the length of s times:
        add the result of find_and_record_substring program to length_list_of_sub_string
        set s to a s that remove the first character
    
    >>return the longest substring without repeating characters
    return longest length equals to the maximum of length_list_of_sub_string
    


  • 코드

  • class Solution:  
        def lengthOfLongestSubstring(self, s: str) -> int:  
            length_of_s = len(s)  
            length_list_of_sub_string = []  
            # program to find each substring without repeating characters in the string
            def find_and_record_substring(str1: str):  
                seen_string = ""  
                seen_dict = {}  
                for char in str1:  
                    if char not in seen_string:  
                        seen_string += char  
                    # if char found in seen_string
                    else:
                        # add the current seen_string to dict first  
                        length_of_seen_string = len(seen_string)  
                        seen_dict.update({length_of_seen_string: seen_string})
                        # clear the seen_string and continue to build seen_string  
                        seen_string = ""  
                        seen_string += char
                # should add the current seen_string to dict
                length_of_seen_string = len(seen_string)  
                seen_dict.update({length_of_seen_string: seen_string})  
                longest_length = max(seen_dict.keys())  
                return longest_length  
            if s == "":  
                return 0  
            while length_of_s != 0:  
                length_list_of_sub_string.append(find_and_record_substring(s))
                # remove the first charcter of s  
                s = s[1::]
                # update the length of s  
                length_of_s = len(s)  
            return max(length_list_of_sub_string)
    


    시도 2(성공)


  • 기본적으로는 위와 같지만 문자열 s에서 고유한 문자의 개수와 같은 하위 문자열의 상한값을 찾는 함수를 추가합니다.
  • 하위 문자열이 상한에 도달하면 함수가 앞으로 이동하지 않고 대신 하위 문자열 길이를 반환합니다
  • .
  • 코드

  • class Solution:  
        def lengthOfLongestSubstring(self, s: str) -> int:  
            length_of_s = len(s)  
            length_list_of_sub_string = []  
            temp_max = 0  
    
            def longest(str1):  
                set1 = set(str1)  
                return len(set1)  
    
            max_limit = longest(s)  
    
            def find_and_record_substring(str1: str):  
                seen_string = ""  
                seen_dict = {}  
                for char in str1:  
                    if char not in seen_string:  
                        seen_string += char  
                    else:  
                        length_of_seen_string = len(seen_string)  
                        seen_dict.update({length_of_seen_string: seen_string})  
                        seen_string = ""  
                        seen_string += char  
                length_of_seen_string = len(seen_string)  
                seen_dict.update({length_of_seen_string: seen_string})  
                longest_length = max(seen_dict.keys())  
                return longest_length  
    
            if s == "":  
                return 0  
            while length_of_s != 0 and temp_max < length_of_s and temp_max < max_limit:  
                length_list_of_sub_string.append(find_and_record_substring(s))  
                s = s[1::]  
                length_of_s = len(s)  
                temp_max = max(length_list_of_sub_string)  
            return max(length_list_of_sub_string)
    


    기타 솔루션


  • Red Crack에서 훨씬 빠른 솔루션

  • def lengthOfLongestSubstring(s: str) -> int:
        # Base condition
        if s == "":
            return 0
        # Starting index of window
        start = 0
        # Ending index of window
        end = 0
        # Maximum length of substring without repeating characters
        maxLength = 0
        # Set to store unique characters
        unique_characters = set()
        # Loop for each character in the string
        while end < len(s):
            if s[end] not in unique_characters:
                unique_characters.add(s[end])
                end += 1
                maxLength = max(maxLength, len(unique_characters))
            else:
                unique_characters.remove(s[start])
                start += 1
        return maxLength
    


    내 반성


  • 그래서 오늘은 Sliding Window Algorithm이라는 새로운 알고리즘을 배웁니다.

  • 신용 거래


  • leetcode3
  • 좋은 웹페이지 즐겨찾기