LeetCode Longest Palindromic Substring (JavaScript)

링크 : https://leetcode.com/problems/longest-palindromic-substring/

문제 설명

Given a string s, return the longest palindromic substring in s.

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.

---

문제 풀이

palindromic : 앞에서 읽거나 뒤에서 읽거나 같은 문자열로 읽히는 것

 

브루트 포스(Brute-Force) 방식을 활용하여 문제 해결

1. check함수 : 시작지점과 끝지점이 주어졌을 때 팰린드롬 문자열인지 확인하는 함수

2. 반복문 (2중 반복문)을 통해 모든 부분 문자열 탐색 (가장 큰 길이의 부분 문자열 부터 검사하므로 먼저 발견한 팰린드롬 문자열이 가장 긴 문자열임)

---

부분 문자열의 길이를 기준으로 탐색

ex) abcdefa (문자열 길이 7)

부분 문자열 길이가 7인 경우 : check(0, 7)

부분 문자열 길이가 6인 경우 : check(0, 6) -> check(1, 7)

...

부분 문자열 길이가 3인 경우 : check(0, 3) -> check(1, 4) -> ... -> check(4, 7)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let check = function  (i, j) {
        let left = i;
        let right = j - 1;

        while (left < right) {
            if (s.charAt(left) !== s.charAt(right)) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }

    for (let end = s.length; end > 0; end--) {
        for (let start = 0; start <= s.length - end; start++) {
            if (check(start, start + end)) {
                return s.substring(start, start + end);
            }
        }
    }

    return '';
};

---

결론

문자열의 특정 부분의 문자를 비교하기 위해 charAt 메서드를 이용

핵심은 부분 문자열을 기준으로 반복문을 통해 검사하는 로직을 작성하는게 포인트인 것 같음

최종적으로 부분 문자열은 substring 메서드를 이용하여 답을 구함