[LeetCode] 3. Longest Substring Without Repeating Characters

신동재·2021년 9월 14일
0

코딩테스트 준비

목록 보기
4/8
post-thumbnail

리트코드 코딩 테스트 준비
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은 중복된 값이 사라지게 되고 최대값을 비교한다.

딕셔너리를 이용한 투포인터 방법도 알아두면 좋을 것 같다. 아직 어떤 문제에 투포인터 알고리즘을 써야하는지는 정확히 모르겠다.

결과는 다 비슷했다.

profile
Software Developer / 1997.12.05

0개의 댓글