[LeetCode] 5. Longest Palindromic Substring
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"이 문제는 두 가지 방법이 있는데 하나는 중심확산법이고 하나는DP이다.나는 잠시 중심 확산법만 제시했을 뿐 DP는 나 자신이 이해하지 못했다.DP든 중심확산법이든 두 가지 서로 다른 케이스를 주의해야 한다. 하나는aba이고 회문 중간에 알파벳이 하나밖에 없다.다른 하나는 abba로 회문 중간에 두 자모가 있다.
시간 O (n^2)
공간 O(1)
1 /**
2 * @param {string} s
3 * @return {string}
4 */
5 var longestPalindrome = function (s) {
6 let res = "";
7 function checkPalindrome(left, right) {
8 while (left >= 0 && right < s.length) {
9 if (s[left] === s[right]) {
10 left--;
11 right++;
12 } else {
13 break;
14 }
15 }
16 left++;
17 right--;
18 if (right - left + 1 > res.length) {
19 res = s.substring(left, right + 1);
20 }
21 }
22
23 for (let i = 0; i < s.length; i++) {
24 if (i > 0 && s[i] === s[i - 1]) {
25 checkPalindrome(i - 1, i);
26 }
27 checkPalindrome(i, i);
28 }
29 return res;
30 };이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
