[Grind75-LeetCode] Longest Palindromic Substring JAVA

반응형

728x90

[Grind75-LeetCode] Longest Palindromic Substring - Medium

---

접근

• 구현

---

풀이

펠린드롬에 관한 문제로 문자열에서 가장 긴 펠린드롬 부분 문자열을 찾아 반환하는 문제다. 이때까지 펠린드롬 문자인지 확인하고 가장 긴 펠린드롬 문자열의 길이를 반환하는 문제를 풀었었다면 부분 문자열 자체를 찾아 반환해야 하는 문제이다. 

    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }

        int start = 0;
        int end = 0;

문자열이 비어있는지 체크를 해 주고 부분 문자열 반환을 위해 펠린드롬의 시작 인덱스와 마지막 인덱스를 담을 변수를 선언했다. 

	for (int i = 0; i < s.length(); i++) {
            int len1 = getPalindromeLength(s, i, i);
            int len2 = getPalindromeLength(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);

각 인덱스마다 인덱스를 기준으로 양쪽으로 검사를 진행하며 구하게 된다. 시작 인덱스가 3이라면 3을 기준으로 한 칸 나아간 2,4 인덱스가 같은지 확인하고 같다면 1,5 또 같다면 0,6과 같이 양쪽으로 확산하는 형태로 검사한다. 그리고 펠린드롬의 경우 짝수 문자열과 홀수 문자열 모두 가능하기 때문에 홀수 문자열인 가운데 문자가 하나 더 있는 경우를 나눠 수행하게 된다. 그렇게 짝수와 홀수 펠린드롬 길이 중 더 큰 길이를 가지고 펠린드롬의 시작 인덱스와 끝 인덱스를 구하고 해당 구간의 부분 문자열을 반환한다. 

    private int getPalindromeLength(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        return end - start - 1;
    }

펠린드롬의 길이를 구하는 메서드이다. 넘겨받은 인덱스로부터 양쪽으로 확산하게 되고 펠린드롬을 만족하는 부분 문자열의 길이를 반환하게 된다. 

---

전체 코드

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }

        int start = 0; 
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = getPalindromeLength(s, i, i);
            int len2 = getPalindromeLength(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 getPalindromeLength(String s, int start, int end) {
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
            start--;
            end++;
        }
        return end - start - 1;
    }
}