파이썬 챌린지: Leetcode 3. 반복되는 문자가 없는 가장 긴 하위 문자열
의문
s
에서 반복되는 문자가 없는 가장 긴 하위 문자열의 길이를 찾습니다. 예시
입력: s = "abcabcbb"
출력: 3
설명: 답은 길이가 3인 "abc"입니다.
입력: s = "bbbbbb"
출력: 1
설명: 정답은 길이가 1인 "b"입니다.
입력: 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(성공)
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)
기타 솔루션
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
내 반성
신용 거래
Reference
이 문제에 관하여(파이썬 챌린지: Leetcode 3. 반복되는 문자가 없는 가장 긴 하위 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/mathewchan/python-challenge-leetcode-3-longest-substring-without-repeating-characters-el8텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)