티스토리 뷰
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
생각의 흐름
일단 가장 쉬운 풀이를 생각해보았다. 시작점과 길이를 바꿔가면서 2중 for문으로 풀면 풀릴것같았다. 다만 중복 계산이 너무 많다. 이전에 계산했던 결과를 이용하면 그 다음 문제를 해결하는데 사용할 수 있다.
어떻게 하면 중복 계산을 제거할 수 있을까 고민하던 찰나에, 팰린드롬의 특성을 이용해보자는 생각이 들었다. 팰린드롬은 양끝을 제외한 가운데 부분이 팰린드롬이고 양끝이 같으면 그 부분은 팰린드롬이다. 이 점을 이용하면 중복 계산을 줄일 수 있을거란 생각이 들었다.
우선 2차원 배열을 선언한뒤, 시작점과 길이를 계속 바꿔가면서 문자열의 시작 인덱스와 끝 인덱스로 잘랐을때 해당 부분이 팰린드롬인지를 아닌지를 기록했다.
그럼 길이가 2일때 구해놨던 정보들이 길이가 3일때 해당 부분이 팰린드롬인지 판단할때 중복계산을 막아 줄 수 있기 때문에 어느정도 계산량을 줄일 수 있었다. 다만 이렇게 해도 퍼센티지가 너무 낮은걸 보니 별로 좋지 못한 풀이인것같다.
var longestPalindrome = function(s) {
const dp = Array(s.length).fill(true).map(() => Array(s.length).fill(true));
let resultLeft=0, resultRight=0;
let MAX = 1;
for(let len=2; len<=s.length; len++) {
for(let left=0; left<=s.length - len; left++) {
const right = left + len - 1;
if(s[left] === s[right] && dp[left+1][right-1]){
dp[left][right] = true;
if(MAX < right - left + 1) {
MAX = right - left + 1;
resultLeft = left;
resultRight = right;
}
}
else {
dp[left][right] = false;
}
}
}
return s.slice(resultLeft, resultRight+1);
};
'알고리즘' 카테고리의 다른 글
[트리] 이진 트리의 최대 깊이 (104. Maximum Depth of Binary Tree) (0) | 2020.06.21 |
---|---|
[트리] 왼쪽 잎들의 합을 구하기(404. Sum of Left Leaves) (0) | 2020.06.21 |
longest-substring-without-repeating-characters (0) | 2020.05.30 |
[leetcode] 추천 75문제 중 1번. twoSum (0) | 2019.12.12 |
3613번 Java vs C++ (0) | 2019.12.03 |
댓글
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- hydrate
- typescript
- useRef
- type alias
- mobx
- server side rendering
- state
- design system
- Babel
- atomic design
- return type
- Next.js
- reducer
- reflow
- rendering scope
- webpack
- props
- react hooks
- computed
- es6
- Action
- await
- useEffect
- javascript
- react
- Polyfill
- reactdom
- promise
- async
- storybook
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
글 보관함