박종훈 알고리즘 블로그

(Leetcode) 3 - Longest Substring Without Repeating Characters

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.


https://leetcode.com/problems/longest-substring-without-repeating-characters/

문자열과 관련된 문제이다.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0

        characters = list(s)
        longest = -1

        def findLongestSubstring(start):
            exist = {}
            length = 0
            for i in range(start, len(characters)):
                if characters[i] in exist:
                    return length
                else:
                    exist[characters[i]] = True
                    length += 1
            return length

        for i, char in enumerate(characters):
            longest = max(longest, findLongestSubstring(i))

        return longest

한번에 통과는 하였지만 매우 결과가 안좋게 나왔다.

그래서 다른 사람의 코드를 확인해보았다.

다른 사람들이 푼 방식

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0

        temp = []
        longest = 0

        for char in s:
            if char in temp:
                temp = temp[temp.index(char) + 1:]
            temp.append(char)
            longest = max(longest, len(temp))

        return longest

똑똑하게 접근한 것 같다.

temp를 통해 최대로 긴 문자열을 저장해두고, 동일한 글자가 나오면 앞에서 해당 글자를 제거하고 뒤에 해당 글자를 추가하는 방식을 택하였다.

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , python , algorithm , Leetcode , string , char , character