Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 5. Longest Palindromic Substring 본문
문제 설명
Given a string s
, return the longest palindromic substring in s
.
palindromic: A string is palindromic if it reads the same forward and backward.
입출력 예
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints
1 <= s.length <= 1000
s
consist of only digits and English letters.
내 솔루션
- i, j 순환하면서 word를 구하고 그 word가
palindromic
인지 체크하는 솔루션 - 처음엔 느려서 Time Limit에 걸려서 최적화한다고 고행 좀했다.
- 큰 단어부터 찾기 때문에 그 이하 단어 찾기는 버려도 된다. 처음 찾은 단어가 가장 큰단어가 됨.
answer
length를 slice로 단어를 뽑기전에 길이를 체크하여check()
를 돌리지 않게 한다.
var longestPalindrome = function(s) {
const check = (str) => {
if(str.length === 0) return false;
let palindromic = true;
for(let i = 0; i < str.length/2; i++){
if(str[i] !== str[str.length-i-1]){
palindromic = false;
break;
}
}
return palindromic;
}
let answer = '';
if(s.length === 1) return s;
for(let i = s.length + 1; i > 0; i--) {
for(let j = 0; j < i; j++) {
if(i - j + 1 > answer.length){
const word = s.slice(j, i);
if(check(word)) {
answer = word;
break;
}
}
}
}
return answer;
};
감상평
- 최적화를 어떻게 할지 고민하는 시간이 쫄리면서도 즐거웠다.
'coding test > leetCode' 카테고리의 다른 글
[leetCode/JS] 46. Permutations (0) | 2022.11.24 |
---|---|
[leetCode/JS] 13. Roman to Integer (0) | 2022.11.24 |
[leetCode/JS] 224. Basic Calculator (0) | 2022.11.24 |
[leetCode/JS] 2047. Number of Valid Words in a Sentence (0) | 2022.11.24 |
[leetCode/JS] 9. Palindrome Number (0) | 2022.11.23 |
0 Comments