leetcode - Longest Palindromic Substring[Java]

문제 출처: 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.

문제 풀이

class Solution {
    public String longestPalindrome(String s) {
        String answer = "";
        for(int j = 0; j < s.length(); j++) {
            for(int i = 0; i < s.length() - j; i++) {
                if(palindrome(j, s.length() - i - 1, s)) {
                    answer = s.length() - i - j > answer.length() ? s.substring(j, s.length() - i) : answer; 
                    if(i == 0)
                        return answer;
                }
            }
        }
        return answer;
    }
    
    public boolean palindrome(int front, int back, String s) {
        
        int frontIndex = front;
        int backIndex = back;
        int mainIndex = 0;
        int backcount = (s.length() - 1) - back;
        int len = (s.length() - front - backcount) / 2;
        while(mainIndex < len) { 
            
            if(s.charAt(frontIndex) != s.charAt(backIndex))
                return false;
            
            frontIndex++;
            backIndex--;
            mainIndex++;
        }
        return true;
    }
}

전에 프로그래머스에서 푼 가장 긴 팰린드롬 문제의 풀이법을 그대로 조금 가독성이 더 좋게 바꿔서 구현을 했는데, 시간 초과가 나와서

	if(i == 0)
       return answer;

위 코드를 추가해 조금 더 최적화를 해주니 겨우 통과했다. 다 풀고 나서 leetcode에서 제공하는 풀이법 중에 아래 방법이 간결하고 runtime이 훨씬 빨라서 참고 해보았다.

나은 풀이

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

위 방식은 주어진 문자열이 팰린드롬이 되기위해 몇개의 center를 가지고 있냐는 관점에서 문제를 해결한다.

문자열의 길이가 n일때 총 2n - 1의 center가 존재한다.

ex) "abcd" 의 총 center의 수는 7개 이다

a, b, c, d 각각 center가 될 수 있다 --> 4개

a와b의 사이, b와c의 사이, c와d의 사이가 center가 될수 있다 --> 3개

총 center 개수만큼 스캔 후 가장 긴 팰린드롬의 substring index를 저장하여 반환한다.