리트코드 코딩 테스트 준비
https://leetcode.com/problems/longest-substring-without-repeating-characters/
문제에 대한 자세한 설명은 다음 사이트에서 확인 할 수 있다.
Given a string s, find the length of the longest substring without repeating characters.
예를 들어 string s가 abcabcbb 라면 output : 3을 출력한다 왜냐하면 가장 긴 abc 문자열의 길이가 3이기 때문이다
Dynamic Programming(DP)를 이용해야 한다. 동적 계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘의 설계 기법이다. 이 문제도 답의 개수를 세야하기 때문에 DP가 적합하다. 불필요한 계산을 줄이고 효율적으로 최적해를 찾는 과정이다.
작은 문제들이 반복됨을 확인 할 때 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용하여 전체 문제를 해결한다.
1.단순화 -> 부분 문제 정의
2.재귀적인 구조 점화식 만들기
3.작은 문제를 해결한 방법으로 전체 문제 해결
DP 에서 주로쓰는 Memoization은 함수의 값을 계산한 뒤 그 값을 배열에 저장하는 방식이다.
https://wooder2050.medium.com/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0
자세한 내용은 여기를 보면서 공부하였다.
같은 문자가 두번이상 나오면 안되고
연속된 substring만을 카운팅해야한다.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
str_list = []
max_length = 0
for x in s :
if x in str_list :
str_list = str_list[str_list.index(x) + 1:]
str_list.append(x)
max_length = max(max_length,len(str_list))
return max_length
DP를 이용한 방법(쓰고 싶었는데 코드로 구현하기가 힘들었다)
def lengthOfLongestSubstring(self, s: str) -> int:
"""
abcdabcdeabcdefg
a bcd a ertyui a bcdefghj i
"""
dp = [1] * len(s) # longest substring length including s[i]
mapping = {}
if s:
mapping[s[0]] = 0
for i, char in enumerate(s[1:], start=1):
if char not in mapping:
mapping[char] = i
dp[i] = dp[i-1] + 1
else:
previous_idx = mapping[char]
# for cases like: abba
# at index 3 (second a) i - previous_idx = 3 but the longest sequence is 2
#
# because we did not consider whether there is other duplicate character between the two letters
# so we need to compare with previous longest substring + 1 (suppose that the new char is not in previous longest substring,
# if previous_longest_substring contains the character, we still get the correct result from the first number i - previous_index )
dp[i] = min(i - previous_idx, dp[i-1] + 1)
mapping[char] = i
return max(dp) if dp else 0
Sliding Window (Two Pointer) 방법
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
answer = 0
lc = 0
dict = {}
max_len = 0
for rc,val in enumerate(s) :
if val in dict and lc <= dict[val] :
lc = dict[val] + 1
else :
max_len = max(max_len,rc-lc+1)
dict[val] = rc
return max_len
간단하게 중복된 값이 존재하면 처음에 중복된 값이랑 같은 문자열 다음열 부터로 substring의 index를 바꿔준다.
그러면 substring은 중복된 값이 사라지게 되고 최대값을 비교한다.
딕셔너리를 이용한 투포인터 방법도 알아두면 좋을 것 같다. 아직 어떤 문제에 투포인터 알고리즘을 써야하는지는 정확히 모르겠다.
결과는 다 비슷했다.