LeetCode - Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

 

나의 풀이

 

class Solution {
    public String longestPalindrome(String s) {
        String ans = String.valueOf(s.charAt(0));
        String temp = "";
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                temp = expand(s, i, i + 1);
                ans = ans.length() < temp.length() ? temp : ans;
            }
            if (i + 2 < s.length() && s.charAt(i) == s.charAt(i + 2)) {
                temp = expand(s, i, i + 2);
                ans = ans.length() < temp.length() ? temp : ans;
            }
        }
        return ans;
    }
    
    public String expand(String s, int left, int right) {
        while (left - 1 >= 0 && right + 1 < s.length() && s.charAt(left - 1) == s.charAt(right + 1)) {
            left--;
            right++;
        }
        return s.substring(left, right + 1);
    }
}

 

 

떠올린 생각

1. brute force

- time complexity : O(n^3)

- logic : 나눌 수 있는 모든 문자열로 나눈 다음 (이중 for 문), 생성된 문자열마다 palindrome 체크

- 당연히 더 좋은 풀이를 떠올려야 한다

 

2. small to big

- time complexity : O(n^2)

- mindset : palindrome은 밖에서 부터 줄여서 체크하는 것보다 작은 단위에서 옆을 확인하며 넓히는 것이 최선이라 생각

- logic : 중간에 겹치는 부분이 1개인 경우와 2개인 경우로 구분해서 매번 확장할 수 있는 만큼 확장

- defect : 최악의 경우 모든 문자열이 하나의 문자로 구성되어 있을 때, 모든 분기마다 최대로 확장되어 로직 상의 중복이 생김

 

결과

 

 

---

다른 사람의 풀이

1. expand from center

class Solution {
    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;
    }
}

- 나의 풀이와 같은 방식이지만 초기 i, i+1 또는 i, i + 2의 동일 조건 또한 메서드 내에서 통일해서 코드 중복을 줄였다

 

 

2. Manacher's Algorithm

class Solution {
    public String longestPalindrome(String s) {

        // code line +8 to line +15
        int strLen = 2 * s.length() + 3;
        char[] sChars = new char[strLen];

        /*
         * To ignore special cases at the beginning and end of the array
         * "abc" -> @ # a # b # c # $
         * "" -> @#$
         * "a" -> @ # a # $
         */
        sChars[0] = '@';
        sChars[strLen - 1] = '$';
        int t = 1;
        for (char c : s.toCharArray()) {
            sChars[t++] = '#';
            sChars[t++] = c;
        }
        sChars[t] = '#';

        int maxLen = 0;
        int start = 0;
        int maxRight = 0;
        int center = 0;
        int[] p = new int[strLen]; // i's radius, which not includes i
        for (int i = 1; i < strLen - 1; i++) {
            if (i < maxRight) {
                p[i] = Math.min(maxRight - i, p[2 * center - i]);
            }

            // expand center
            while (sChars[i + p[i] + 1] == sChars[i - p[i] - 1]) {
                p[i]++;
            }

            // update center and its bound
            if (i + p[i] > maxRight) {
                center = i;
                maxRight = i + p[i];
            }

            // update ans
            if (p[i] > maxLen) {
                start = (i - p[i] - 1) / 2;
                maxLen = p[i];
            }
        }

        return s.substring(start, start + maxLen);
    }
}

- time complexity : O(n)

- space complexity : O(n)

- logic : 다음의 팰린드롬이 이전의 팰린드롬의 범위 내에 있다면, mirror에 해당하는 수치는 무조건 넘는다 (단, 오른쪽 범위를 안넘는 한)

              위의 규칙을 토대로 중복되는 계산 없이 팰린드롬을 찾아간다.

- 아래 영상이 가장 로직을 잘 설명해주는 것 같다.