[LeetCode] 5. Longest Palindromic Substring - Java

https://leetcode.com/problems/longest-palindromic-substring/description/

Longest Palindromic Substring - LeetCode

---

문제

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

 

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

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

---

풀이

풀이 과정

숫자와 알파벳으로 이루어진 문자열 s가 주어질 때 s의 부분 문자열 중 가장 긴 palindrome(회문)을 구하는 문제이다.
palindrome은 거꾸로 읽어도 원래와 똑같은 문자나 문장을 의미한다.

투 포인터를 이용하여 palindrome을 판단하는 함수를 생성한다.
문자열 s와 왼쪽, 오른쪽 인덱스를 가지고 인덱스를 양쪽으로 늘려가며 해당 인덱스에 해당하는 문자가 같은지 판단하고 palindrome이 될 수 있는 최대 인덱스에서 문자열을 잘라 return 한다.

/**
     * @param s         탐색할 문자열
     * @param left      탐색을 시작할 왼쪽 인덱스
     * @param right     탐색을 시작할 오른쪽 인덱스
     * @return
     */
    public String isPalindrome(String s, int left, int right) {
        // 왼쪽 인덱스와 오른쪽 인덱스가 끝에 도달할 때 까지 반복
        while(left >= 0 && right < s.length()) {
            // 양쪽의 글자가 같은 경우 인덱스를 한칸씩 이동
            if(s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } 
            // 양쪽의 글자가 다른 경우 탐색 종료
            else {
                break;
            }
        }
        
        // 인덱스가 이동한 상태로 탐색이 종료되었으므로 이전 인덱스까지 문자열을 잘라서 return
        return s.substring(left + 1, right);
    }
}

 

생성한 함수를 이용하여 주어진 문자열 s의 모든 문자에서 palindrome을 판단해야하는데 문자열의 길이가 홀수인 경우와 짝수인 경우를 나누어 생각해야한다.
문자열의 길이가 홀수인 경우에는 같은 인덱스에서 시작하여 양쪽을 비교하면 되고,
문자열의 길이가 짝수인 경우에는 인접한 두 인덱스에서 시작하여 양쪽을 비교하여야한다.
각각의 경우에서 나온 Palindrome의 길이와 Longest Palindromic Substring의 길이를 비교하여 더 큰 값으로 정답을 갱신한다.

// Longest Palindromic Substring
String lps = "";

// 문자열의 모든 문자 탐색
for(int i = 0; i < s.length(); i++) {
    // 각 문자부터 양쪽으로 늘려가며 palindrome 체크
    // 홀수인 경우 
    String oddMax = isPalindrome(s, i, i);
    lps = (lps.length() < oddMax.length())? oddMax : lps;
    // 짝수인 경우
    String evenMax = isPalindrome(s, i, i + 1);
    lps = (lps.length() < evenMax.length())? evenMax : lps;
}

 

모든 탐색이 종료되면 결과값을 return 한다.

return lps;

---

최종 코드

class Solution {
    public String longestPalindrome(String s) {
        // Longest Palindromic Substring
        String lps = "";
        
        // 문자열의 모든 문자 탐색
        for(int i = 0; i < s.length(); i++) {
            // 각 문자부터 양쪽으로 늘려가며 palindrome 체크
            // 홀수인 경우 
            String oddMax = isPalindrome(s, i, i);
            lps = (lps.length() < oddMax.length())? oddMax : lps;
            // 짝수인 경우
            String evenMax = isPalindrome(s, i, i + 1);
            lps = (lps.length() < evenMax.length())? evenMax : lps;
        }

        return lps;
    }

    /**
     * @param s         탐색할 문자열
     * @param left      탐색을 시작할 왼쪽 인덱스
     * @param right     탐색을 시작할 오른쪽 인덱스
     * @return
     */
    public String isPalindrome(String s, int left, int right) {
        // 왼쪽 인덱스와 오른쪽 인덱스가 끝에 도달할 때 까지 반복
        while(left >= 0 && right < s.length()) {
            // 양쪽의 글자가 같은 경우 인덱스를 한칸씩 이동
            if(s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } 
            // 양쪽의 글자가 다른 경우 탐색 종료
            else {
                break;
            }
        }
        
        // 인덱스가 이동한 상태로 탐색이 종료되었으므로 이전 인덱스까지 문자열을 잘라서 return
        return s.substring(left + 1, right);
    }
}

---