[21/10/06] Longest Substring Without Repeating Characters By Sliding Window
문제
코드
1차 코드
문자열을 한개로 쪼갤때, 두개로 쪼갤때 -> 마다 문자열을 전부 쪼개어 중복이 있는지 없는지 검사한 후 중복이 없는 것이 있다면 answer을 갱신한다.
최악의 경우 n^2 * (slice하는 시간 + 중복 체크를 위해 set을 만드는 시간) 비효율적이다.
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if(s.length === 0) return 0;
let answer = 1;
for(let num = s.length-1;num>=0;num--){
for(let i=0;i<= s.length - (num+1);i++){
if(!isDuplicate(s.slice(i,i+(num+1)))){
return num+1;
}
}
}
function isDuplicate(s){
const array = s.split("");
return [...new Set(array)].length !== array.length
}
};
2차 코드
슬라이딩 윈도우를 적용해보았다. O(n)시간에 끝낼 수 있다.
var lengthOfLongestSubstring = function(s) {
const chars = [];
let answer = 0;
for(let i=0;i<s.length;i++){
while(chars.indexOf(s[i]) !== -1){
// 중복되는 것이 나왔다면, 해당 문자를 지우지 않는 이상 모두 불가능하다. 따라서 큐에 넣었던 걸 다 삭제하고 (중복문자까지) 다시 시작한다고 생각해야함.
// 최악의 경우 n의 시간이 소비되지만, 최악의 경우라면 이전 반복에서 이 반복문을 실행하지 않게 된다.
chars.shift();
}
chars.push(s[i]);
answer = Math.max(chars.length,answer);
}
return answer;
};
//while 문을 다음과 같이 작성하면 살짝 성능이 떨어진다. -> 반복문에 항상 들어가고 항상 break를 실행시켜서 그런가..?
while(true){
if(chars.indexOf(s[i]) === -1){
break;
}
chars.shift();
}
map 객체를 이용하여 풀수도있다. left - right 가 window의 범위이다.
var lengthOfLongestSubstring = function (s) {
let map = new Map();
let left = 0;
let max = 0;
for(let right=0;right<s.length;right++){
const char = s[right];
if(map.has(char) && map.get(char) >= left){
// 중복이 발생한 이 후 부터 다시 시작.
// 중복이 발생한 문자이면서 현재 문자 범위에 속해있다면 left를 그 문자 위치 + 1해주어야한다.
left = map.get(char) + 1;
}else{
// 처음 등장한 문자이거나, 중복이 발생하였으나 현재 문자 창 범위에 있지 않은 경우
max = Math.max(max,right-left + 1);
}
map.set(char,right);
}
return max;
};
슬라이딩 윈도우 - 손 코딩
Author And Source
이 문제에 관하여([21/10/06] Longest Substring Without Repeating Characters By Sliding Window), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/211006-Longest-Substring-Without-Repeating-Characters-By-Sliding-Window저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)