리트코드에서 새로운문제를 가져왓습니다.
리트코드는 근데 왜 난이도순으로 번호가 안매겨져있는지.......휴..
Longest Substring Without Repeating Characters
def lengthOfLongestSubstring(self, s: str) -> int:
char_index = {} # 문자와 해당 문자의 인덱스 값을 저장할 해시맵
max_len = 0 # 최대 부분 문자열 길이
start = 0 # 슬라이딩 윈도우의 시작 인덱스
for end in range(len(s)):
# 현재 문자가 이미 딕셔너리에 있고 슬라이딩 윈도우 값보다 크거나 같을 때
# 즉, 중복된 문자열이 등장했을 때
if s[end] in char_index and char_index[s[end]] >= start:
# 슬.윈 시작 위치를 갱신
start = char_index[s[end]] + 1
# 현재 문자의 인덱스를 딕셔너리에 업데이트
char_index[s[end]] = i
# 현재 윈도우 길이를 계산하여 최대 길이와 비교
max_len = max(max_len, end-start+1)
return max_len
for문, 특히 char_index[s[i]]를 작성해야한다는 것을 나혼자선 절대 모를것같다. char_index[i] 정도로 짜고 왜틀렷지 하고잇을듯,, 그래서 추가설명!
🪄 주어진 문자열: abcabcbb
초기에 start는 0이며, char_index는 빈 딕셔너리입니다.
end == 0일때, s[0] = a이므로 딕셔너리에 a 추가. start(윈도우의 길이) = 1
end == 1일때, s[1] = b이므로 딕셔너리에 b 추가. start = 2
end == 2일때, s[2] = c이므로 딕셔너리에 c 추가. start = 3
end == 3일때, s[3] = a로 중복되는 문자이므로 추가X. 기존 a의 위치였던 0에 1을 더해 b부터 문자열을 다시 탐색
a의 인덱스 번호를 3으로 갱신
길이 비교 후 다시 for문 실행
💡 char_index가 완성되는 구체적인 과정
문자열: a b c a b c b b
인덱스: 0 1 2 3 4 5 6 7
# 초기 상태
char_index = {}
# end = 0
s[0] = 'a'
char_index = {'a': 0}
# end = 1
s[1] = 'b'
char_index = {'a': 0, 'b': 1}
# end = 2
s[2] = 'c'
char_index = {'a': 0, 'b': 1, 'c': 2}
# end = 3
s[3] = 'a'
char_index = {'a': 3, 'b': 1, 'c': 2}
# end = 4
s[4] = 'b'
char_index = {'a': 3, 'b': 4, 'c': 2}
# end = 5
s[5] = 'c'
char_index = {'a': 3, 'b': 4, 'c': 5}
# end = 6
s[6] = 'b'
char_index = {'a': 3, 'b': 6, 'c': 5}
# end = 7
s[7] = 'b'
char_index = {'a': 3, 'b': 7, 'c': 5}
끝