문제

Longest Palindromic Substring - LeetCode

Code

풀이-1

class Solution {
    public String expand(int left, int right, String s){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }

        return s.substring(left + 1, right);
    }

    public String longestString(String str1, String str2, String str3){
        List<String> stringList = new ArrayList<>();
        stringList.add(str1);
        stringList.add(str2);
        stringList.add(str3);

        stringList.sort(Comparator.comparing(String::length));
        return stringList.get(stringList.size() - 1);
    }

    public String longestPalindrome(String s) {
        if (s.length() < 2){
            return s;
        }

        String result = "";
        for (int i=0; i < s.length(); i++){
            result = longestString(expand(i, i, s), expand(i, i+1, s), result);
        }

        return result;
    }
}

1. 투 포인터를 활용하여 다이내믹하게 윈도우의 크기를 변화해가면서 palindrome를 확인한다.
   1. longestPalindrome 함수에서는 시작점을 문자열 처음부터 끝까지 이동하면서 expand 함수를 실행한다.
   2. expand 함수를 통해 two pointer를 양 옆으로 늘려가면서 palindrome을 확인한다.
   

풀이-2

class Solution {
    public String expand(int left, int right, String s){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }

        return s.substring(left + 1, right);
    }
    
    public String longestPalindrome(String s) {
        if (s.length() < 2){
            return s;
        }

        String result = "";
        for (int i=0; i < s.length(); i++){
            result = Stream.of(expand(i, i, s), expand(i, i+1, s), result)
                    .max(Comparator.comparingInt(String::length))
                    .orElse("");
        }

        return result;
    }
}

1. expand(i, i, s), expand(i, i+1, s), result중 가장 길이가 긴 값을 Stream을 이용하여 구하였다.
   1. 아직 Stream은 어렵다..