[21/08/20 KATA NINJA] leet code #3 longest palindrome
Longest Palindrome
가장 큰 펠린드롬을 찾는 문제이다.
worst case
그냥 떠오르는데로 문제를 풀었더니, 시간초과발생. O(n^3)
//brute force
// check palindrome n
function isPanlin(str){
return str === str.split("").reverse().join("");
}
let answer;
let max = 0;
let idx = 0;
// n^2
for(let idx = 0;idx<s.length;idx++){
if(max >= s.length - (idx)){
break;
}
for(let check=s.length;check>=idx;check--){
let tar = s.substring(idx,check)
if(isPanlin(tar) ){
// 회문검사 비용이 너무크다 이를 디피로 줄여야함
if(max < tar.length){
answer = tar;
max = tar.length;
}
}
}
}
위 코드는 문자열을 n^2번 순회하면서 나오는 문자열을 펠린드롬 체크함수에 넣어 체크한 후 가장 크면 저장하는 방식의 코드이다.(Brute Force)
return string.split('').reverse().join('')
이 코드가 O(n+k)의 복잡도를 가짐
// Time Complexity = Possibly O(n+k)
// Since these are inbuilt methods, we can't be 100% sure of how
// JavaScript is handling them. But since .reverse() involves
// traversing through an array, it possibly has time complexity
// of O(n).
// So we can represent the time complexity as O(n+k), where k is a
// constant to heuristically denote the complexity of the other two
// methods.
n^2까지는 어쩔 수 없음. 펠린드롬 검사를 O(n) -> O(1)로 줄여야한다.
Success Case
Dynamic Programming의 방식을 적용
펠린드롬은 앞뒤가 같으면서 앞 뒤를 자른 나머지 안의 문자들이 회문이면 회문이다. 이것에서 아이디어를 얻어 디피 방식으로 생각해보면 다음과 같이 구현할 수 있다.
문자가 두개인 경우 -> 문자가 세개인 경우 -> ... 로 나아가면서 회문인지 아닌지 점검한다.
EX)
문자열 s가 abba
인 경우, i=0 j=3라면, s[0] === s[3] && dp[1][2]가 회문이면(true
이면) dp[0][3]은 회문이다.(true
이다 )
let dp = []
// 문자가 한개인 경우 펠린드롬이다.
// dp[0][3]은 0~3의 문자열의 회문인지 아닌지를 값으로 저장한다.
for(let check=0;check<s.length;check++){
dp[check]= Array(s.length).fill(false);
// character is palindromic
dp[check][check] = true;
}
let left = 0;
let right = 0;
for(let i=1;i<s.length;i++){
// 두개인 경우 -> 세 개인 경우 -> ... 로 나아가며 점검한다.
let j=0;
while(j+i < s.length){
if(s[j] === s[j+i]){
// 앞 뒤 문자가 같으면 펠린드롬일 수 있다.
if(i === 1 || dp[j+1][j+i-1]){
// 문자가 두개인 경우 또는 앞뒤를 짜른 문자열이 회문인 경우
// is Pelindromic
dp[j][j+i] = true;
// 시작할 문자열 인덱스와 끝날 문자열 인덱스를 저장한다.
// 문자가 한개인 경우부터(작은 경우부터) 나아가므로 이 곳에 마지막으로 들어와 저장된 값이 최대 펠린드롬의 인덱스 번호들임.
left = j
right = j+i
}
}
j++;
}
}
return s.slice(left,right+1)
DP와 재귀를 이용하지 않은 코드
function getPelinIndex(type,i){
switch(type){
case 'even':
if(s[i] !== s[i+1]){
// 짝수로 호출되었는데 중앙 데이터들의 값이 다르다면 회문이 아니므로, 그 문자를 회문으로 리턴한다.
left = i;
right = i;
return [left,right];
}else{
// 짝수인데 중앙 데이터들의 값이 같다면 회문 일 수 있으므로 리턴하지 않는다.
// O O O<-(이거말하는거임)->O O O
left = i;
right = i + 1;
}
break;
case 'odd':
// 홀수로 호출하였다면 O O O<--(이거말하는거임) O O
left = i;
right = i;
break;
}
while(left>0 && right < s.length && s[left-1] === s[right+1]){
// left는 줄이고
// right는 올리면서 서로의 값이 같은지 확인한다.(회문조건임)
// O O O O O O
left--;
right++;
}
return [left,right]
}
let left;
let right;
let maxRight = 0;
let maxLeft = 0;
for(let i=0;i<s.length-1;i++){
// even
[left,right] = getPelinIndex('even',i)
if(maxRight-maxLeft < right - left){
// Return한 문자열의 길이가 맥스 값보다 길다면 바꾼다.(최대를 찾아야하므로)
maxRight = right;
maxLeft = left;
}
// odd
[left,right] = getPelinIndex('odd',i)
if(maxRight-maxLeft < right - left){
// Return한 문자열의 길이가 맥스 값보다 길다면 바꾼다.(최대를 찾아야하므로)
maxRight = right;
maxLeft = left;
}
}
return s.slice(maxLeft,maxRight+1)
Author And Source
이 문제에 관하여([21/08/20 KATA NINJA] leet code #3 longest palindrome), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/210820-KATA-NINJA-longest-palindrome저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)