자료구조 · 알고리즘
[Leetcode - String] Longest substring without repeating characters 풀이
eblee
2019. 11. 10. 14:02
문제 링크
https://leetcode.com/problems/longest-substring-without-repeating-characters/
풀이
이 문제는 문자열에서 중복 없이 가장 긴 substring의 길이를 반환하는 문제이다. 내가 접근한 방식은 완전 탐색이다.
자신보다 뒤에 있는 문자열들을 순회하면서 중복이 발생하기 전까지의 길이를 찾아 저장해놓은 max length와 비교하는 로직을 작성했다.
O(N^2)의 시간 복잡도를 가지기 때문에 상대적으로 너무 느리다.
다른 사람들의 풀이를 보았고, O(N)으로 푸는 코드를 찾았다.
이 코드는 각 문자열을 map이라는 객체에 저장하면서 value로 이 문자가 가장 마지막으로 나온 index를 저장한다. 이로 인해 한번 순회로 중복 없는 최대 길이를 구할 수 있다.
정답 코드
var lengthOfLongestSubstring = function (s) {
let maxLen = 0;
let tempLen = 0;
let arr = [...s];
let arrLen = arr.length;
let obj = {};
for(let i=0; i<arrLen; i++) {
obj = {};
tempLen = 0;
for(let j=i; j<arrLen; j++) {
if(obj[arr[j]]) break;
else {
tempLen += 1;
obj[arr[j]] = true;
}
}
maxLen = Math.max(maxLen, tempLen);
}
return maxLen;
};
O(N) code
function lengthOfLongestSubstringBest(s) {
const map = {};
var left = 0;
return s.split('').reduce((max, v, i) => {
left = map[v] >= left ? map[v] + 1 : left;
map[v] = i;
return Math.max(max, i - left + 1);
}, 0);
}