LeetCode - Longest Palindromic Substring

문제 설명

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

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "a"
Output: "a"

Example 3:

Input: s = "ac"
Output: "a"

Constrains

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

Solution

• [첫번째방법] index를 순환하며 해당 index를 기준으로 가능한 가장 긴 palindromic string을 찾음

class Solution {
    public String longestPalindrome(String s) {

        String longgestStr = "";

        if (s.length() == 1) {
            return s;
        }

        for (int i = 0; i < s.length() - 1; i++) {
            String tempLongOdd = findLongest(s, i, i);
            String tempLongEven = findLongest(s, i, i + 1);

            if (tempLongOdd.length() < tempLongEven.length() && longgestStr.length() < tempLongEven.length()) {
                longgestStr = tempLongEven;
            } else if (tempLongOdd.length() >= tempLongEven.length() && longgestStr.length() < tempLongOdd.length()) {
                longgestStr = tempLongOdd;
            }
        }
        return longgestStr;
    }

    public String findLongest(String s, int i, int j) {
        // StringBuffer를 굳이 쓰지 않고 인덱스만 기억해서 substring 가능함
        // StringBuffer strBuilder = new StringBuffer();
        while (i >= 0 && j < s.length()) {
            if (s.charAt(i) != s.charAt(j)) {
                // i와 j가 이미 포함되지 않는 테두리 index이므로 i--, j++를 해주지 않는다.
                break;
            }
            if (i == j) {
                // strBuilder.append(s.charAt(i));
            } else {

                // strBuilder.insert(0, s.charAt(i));
                // strBuilder.append(s.charAt(j));
            }
            i--;
            j++;

        }
        // return strBuilder.toString();
        return s.substring(i + 1, j);
    }
}

• [두번째방법] Brute Force (TC:O(n^3))

  • 기준점을 잡아서 범위를 정하고 가능한 긴 문자열을 찾는 것은 위와 동일하지만, 범위의 시작점과 끝점에 따라 안에 속하는 모든 케이스를 다루다 보니, 시작점, 끝점이 달라져도 여러번 수행되어버린다.
  • 처음에 이렇게 풀어서 accept는 되었지만 TC 속도가 너무 안나와서 다른 방법을 고안해본것이 첫번째방법이다.

class Solution2 {

    public static void main(String[] args) {

        String s = "bb";
        String longestStr = s.substring(0, 1);
        int maxLen = 1;
        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length() - 1; (j > i && j - i + 1 > maxLen); j--) {
                if (Palindrome.checkPalindrome(s, i, j)) {
                    if (maxLen < (j - i + 1)) {
                        longestStr = s.substring(i, j + 1);
                        maxLen = longestStr.length();
                    }
                    break;
                }
            }
            // longestPalindrome(s,i);
        }
        System.out.println(longestStr);
    }
}

class Palindrome {
    public static boolean checkPalindrome(String s, int startIdx, int endIdx) {
        boolean isSame = true;
        // for (int k = startIdx; k <= (endIdx + startIdx) / 2; k++) {
        while (startIdx < endIdx) {
            if (s.charAt(startIdx++) != s.charAt(endIdx--)) {
                isSame = false;
                break;
            }
            // check palindrome
        }
        return isSame;
    }
}