LeetCode 5 Longest Palindromic Substring Medium [Java]

문제: https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

1. 코드

class Solution {
    public String longestPalindrome(String s) {
        int max = 0;
        String answer = "";
        for(int i = 0; i < s.length(); i++) {
            char start = s.charAt(i);
            for(int j = i + 1; j <= s.length(); j++) {
                if(start != s.charAt(j - 1) || max >= j - i) continue;
                String temp = s.substring(i, j);
                StringBuilder sb = new StringBuilder(temp);
                if(temp.equals(sb.reverse().toString())) {
                    max = temp.length();
                    answer = temp;
                }
            }
        }
        return answer;
    }
}

2. 설명

 이중 반복문을 통해서 양 끝의 문자가 동일하고 길이가 max 값보다 크고 회문 검사를 통과하면 해당 문자열을 저장하여 반환하는 방식이다.

3. 추가

추가적으로 알아보니 해당 문제는 투포인터를 사용하는 것이 정석이였다. 코드는 아래와 같다.

class Solution {
    int left, len;
    private void sol(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        if(len < r - l - 1) {
            left = l + 1;
            len = r - l - 1;
        }
    }
    public String longestPalindrome(String s) {
        if(s.length() == 1) return s;
        for(int i = 0; i < s.length() - 1; i++) {
            sol(s, i, i + 1);
            sol(s, i, i + 2);
        }
        return s.substring(left, left + len);
    }
}

양 끝의 문자가 동일하면 확장하는데 짝수와 홀수부분을 고려하여 진행되며 처음 작성된 코드와 다른 점은 회문이 아니라고 판단되면 바로 종료하여 다음 문자에 대한 검사를 진행하는데 처음 작성한 코드의 경우 문자의 처음부터 끝까지 전부 검사한다는 차이가 있다.

위: 투포인터, 아래: 처음 작성한 코드

투포인터를 사용한 경우 14ms가 걸리고 처음 작성된 코드의 경우 390ms가 걸리며 메모리도 더 사용한다.