[Leetcode]Longest Palindromic Substring

주어진 문자열에서 가장 긴 회문문자열(거꾸로해도 똑같은)을 찾는 문제입니다.

접근방법

처음 문제를 보고 가장 단순하게 접근했던 방법은 이중 for문으로 모든 경우의 수를 확인해
자른 문자열을 거꾸로한 문자열과 비교하였다.

if(s.length()==1) return s;
for(int i=0;i<s.length();i++){
	for(int j=s.length();j>=i;j--){
		tmp = s.substring(i,j);
		StringBuilder sb = new StringBuilder(tmp).reverse();
		if(String.valueOf(sb).equals(tmp) && result.length()<tmp.length()){
			result = tmp;
			break;
		}
	}
}

동작은 하지만 당연히 성능이 구리다. 어떻게 하면 좀 더 효율적으로 접근할 수 있을까?
여러 방법이 있겠지만 아래와 같은 방법이 직관적으로 이해가 쉬웠다.

• 거꾸로해도 똑같다는 것은 중간 기준점으로 양옆이 동일하다는 것을 의미
• 기준점으로 부터 양쪽으로 문자열값 비교하여 동일하면 그다음값 비교하는 방법으로 MAX값 도출

직관적으로 이해하기 쉽게 작성했다고 생각한 코드를 공유한다.

class Solution {
    private int lo, maxLen;

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;

        for (int i = 0; i < len-1; i++) {
            extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
            extendPalindrome(s, i, i+1); //assume even length.
        }
        return s.substring(lo, lo + maxLen);
    }

    private void extendPalindrome(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k - j - 1) {
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}

참고자료

https://leetcode.com/problems/longest-palindromic-substring/discuss/2928/Very-simple-clean-java-solution