[leetcode] 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.

문제접근

table을 만들어두고 순회하면서 table에 값이 있을때까지의 cnt를 더하여
가장 큰 값을 반환하게 작업을 1차로 했었는데, 그때 문제는 3번째 문제에서
결과값이 "pw"로 나온다.
이 알고리즘은 wke를 검출하지 못한다.

접근법은 DP라고하는데, DP는 아직까지도 잘 모르겠다.
많이 풀어보면 좀 나아지려나..

우선 내가 푼 방법은
첫번째 접근이랑 비슷하다.
다만 첫번째 접근을 각 문자열마다 계속 돌면서 진행한다는게 다르다.

즉 문자를 하나씩 돌면서 (i) 그 다음문자부터 다시 순회를 돈다 (j)
j는끝까지 갈때까지 돌면서 문자열들을 table에 저장을 하다가,
테이블에 이미 있다면 그때까지의 문자열의 길이를 최대값이랑 비교.
그렇게 i와 j를 계속 순회하면서 진행한다.
table은 i가 증가될때마다 초기화된다.

문제코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: table = set() _max = 0 cnt = 0 for e in s: if e in table: _max = max(_max, cnt) cnt = 0 else: table.add(e) cnt += 1 return _max

소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: answer = 0 if len(s) < 2: return len(s) n = len(s) for i in range(n): j = i tmp_table = set() while j < n: if s[j] in tmp_table: answer = max(answer, len(s[i:j])) break else: tmp_table.add(s[j]) j += 1 if len(tmp_table) == len(s[i:]): answer = max(answer, len(s[i:])) return answer