유명한 알고리즘 문제 팔린드롬 문제입니다! 테스트에선 본 적은 없지만 여러 알고리즘 사이트에 기본적으로 나오는 문제에요. 알아두면 좋은 문제라 생각합니다.

문제

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

제한사항

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

접근

팔린드롬Palindrome이 무엇인지 알면 이해하는데 쉽습니다. 보통 이걸 알고 있다는 건 이미 문제를 풀어봤다는 이야기이기도 하지만요 ㅎㅎ

팔린드롬Palindrome은 문자 배치가 거울처럼 미러링된, 대칭된 문자열입니다. 예제로 설명드리자면,

• "aba" $\to$ O
• "a" $\to$ O
• "adad" $\to$ X
• "aaa" $\to$ O
• "aa" $\to$ O

짝수면 맞는 짝 위치끼리 비교를 하고, 홀수인 경우 짝을 이룰 수 없는 정가운데 문자를 제외하고 비교합니다. 이정도면 팔린드롬에 대한 이해가 충분히 될거라 봅니다.

저는 투 포인터Two Pointer 개념을 사용해 문제를 풀었습니다. left 값을 0, right 값을 문자열 마지막 인덱스로 주고 substring을 통해 팔린드롬Palindrome인지 확인을 하고 맞으면 찾은 답보다 길면 답에 초기화하고 left를 증가시켜 기준점을 새로 하고 substring 을 구성해 답을 찾고, 아니면 right를 빼주는 식으로 전개했어요.

답안

class Solution{
    public boolean IsPalindrome(String s){
        int left = 0, right = s.length() - 1;
        while(left < right){
            if(s.charAt(left) != s.charAt(right))
                return false;
            ++left;
            --right;
        }
        return true;
    }

    public String longestPalindrome(String s) {
        if(s.length() <= 1)
            return s;

        String answer = "";
        int left = 0, right = s.length() - 1;
        while(left <= right){
            String subStr = s.substring(left, right + 1);
            if(answer.length() >= subStr.length()) {
                ++left;
                right = s.length() - 1;
                continue;
            }

            if(IsPalindrome(subStr)){
                answer = subStr;
                ++left;
                right = s.length() - 1;
            }
            else{
                --right;
            }
        }
        return answer;
    }
}