[Python/LeetCode]코딩테스트 준비를 위한 파이썬 알고리즘 문제 3.longest substring without repeating characters 해설(medium level)

문제 3. longest substring without repeating characters

Given a string, find the length of the longest substring without repeating characters.
Example 1:Input: "abcabcbb"
Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:Input: "bbbbb"
Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

 

주어진 문자열에서 중복없이 연이어 나올 수 있는 문자열 중 가장 긴 문자열을 찾으면 됩니다.

문제 1. two sum 을 풀 때 enumerate 함수를 사용했기 때문에 다른 방식으로 풀어보려고 시도해보았습니다.

 

def makesubstring(list_input):
        ans = []
        #input되는 리스트의 길이를 구하고, ans 내부에 존재하지 않는 경우 ans에 해당 글자를 넣어줍니다.
        for i in range(len(list_input)) :
            if list_input[i] not in ans :
                ans.append(list_input[i])
            
        string_ans = ''.join(ans)
        
        #join함수를 통해 최종 결과를 str로 출력합니다.
        return string_ans
        
class Solution:
    
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # 사전에 생성해둔 함수를 사용하기위해 str형 input인 s를 list로 바꿔준 뒤 결과를 저장합니다.
        input_string = list(s)
        substring = makesubstring(input_string)
        check_box = []
                     
        #결과 단어 substring이 주어진 문자열에 없는 경우(순서가 잘못된 경우)
        if s.find(substring) == -1 :
           	
            for i in range(len(s)):
                for j in range(len(s)):
                    
                    #list slice시 list[i:j] 일 때 i>j인 상황을 회피 
                    if i > len(s)+1 -j :
                        pass
                    
                    else:
                        check_list = input_string[i:len(s)+1-j]
                        check_ans = makesubstring(check_list)
                        
                        if s.find(check_ans) == -1 :
                            pass
                            
                        else :
                            check_box.append(len(check_ans))
            
            return max(check_box)
        
        #결과 문자열 substring이 주어진 문자열 s에 있는 경우 바로 길이를 출력
        else :
            return len(substring)
            
                       
                            
                        

 

결과는 모두 correct answer가 나오지만, 문자열의 길이가 길어지니 time limit exceeded가 나와버렸습니다 :(

혹시나 enumerate를 사용하지 않고 훌륭하게 문제를 풀어낸 답안이 있는지 확인해보았지만, 결국 사람이 생각하는 건 다 거기서 거기인가봅니다...대부분 enumerate를 사용했더군요. 

그래서 저도 그냥 다시 enumerate를 사용해보겠습니다.

 

class Solution:
    
    def lengthOfLongestSubstring(self, s):
        
        dic = {} 
        index = 0
        start = 0
        
        for i, word in enumerate(s):
            
            if word in dic:
                # word가 위치한 부분까지의 길이
                index = max(index, i-start)
                
                # start위치를 word의 index로 옮기기
                start = max(start, dic[word]+1)
            
            # word를 dic에 넣기 
            dic[word] = i
        
        return max(index, len(s)-start)

문자열에서 enumerate를 사용해 각각의 값(word)과 위치를 반환받고, dic에 존재하는지를 검사합니다.

검사 결과 존재한다면, index변수를 값이 존재하는 부분의 값으로 바꿔줍니다. 

마찬가지로 start변수 역시 값의 다음 부분부터 검사할 수 있도록 index변수 위치로 수정해줍니다.

 

 

확실히 loop 사용이 줄어드니까 전체적인 코드길이나 가독성이 훨씬 좋아지긴 합니다.

list와 loop을 다루는 경우 이와 같이 enumerate의 사용이 매우 쉽고 편합니다. 다른 방법을 찾는 것도 좋지만, 사용하기 가장 쉽고 편한 방법을 찾아가는 python의 취지에 맞게 그냥 편한걸 사용합시다.

 

http://github.com/Leo-bb/LeetCode

Leo-bb/LeetCode