📌 문제

String s= "123454327"

위와 같이 string이 있다고 가정하면,

2345432

가 가장 긴 회문(palindrome)이다.

가장 긴 회문값을 반환하라

🔥 문제링크

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

📌 아이디어

🔥 2 pointer, 3 pointer 이용

위와 같이 두 개의 포인터가 전진을 나간다.
만약 회문에 걸린다면, 그 자리에서 확장을 해나가면 된다.

2개의 포인터를 쓰는 이유는 회문이 짝수 형태일 수도 있고, 홀수 형태일 수도 있기 때문이다.

그 중 가장 길이가 긴 문자열을 반환한다.

🔥 tip

s[::-1] # 문자열 거꾸로 뒤집기

max_value = max(max_value,expand(i,i+1),expand(i,i+2),key=len)
# 가장 긴 문자열을 저장

📌파이썬 코드

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

def longestPalindrome(s):
    if len(s)<2 or s == s[::-1]:
        return s
    max_ = ""
    for i in range(len(s)):

        max_ = max(max_,expand(i,i+1,s),expand(i,i+2,s),key=len)
    return max_

def expand(left,right,s):
    while left>=0 and right<len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left+1:right]


palindrome= longestPalindrome("babad")
print(palindrome)

🔥 제출한 코드

class Solution:
    def longestPalindrome(self,s):
        def expand(left,right,s):
            while left>=0 and right<len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        if len(s)<2 or s == s[::-1]:
            return s
        max_ = ""
        for i in range(len(s)):
            max_ = max(max_,expand(i,i+1,s),expand(i,i+2,s),key=len)
        return max_
        

📌 Java코드

public class LongestPalindrome {
    public static void main(String[] args) {
        String s = "123454327";
        String s2 = "122134567";
        System.out.println(solution(s2));
    }
    public static String solution(String s){
        String result= "";

        for(int i=0;i<s.length()-1;i++){
            String twoPointer = expand(i,i+1,s);
            String threePointer = expand(i,i+2,s);
            String temp="";

            if(twoPointer.length()>threePointer.length()){
                temp = twoPointer;
            }else{
                temp = threePointer;
            }
            if(result.length() <=temp.length()){
                result = temp;
            }
        }
        return result;
    }
    public static 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);
    }
}

🔥 주의점

파이썬에서는 slicing이 index를 넘어가도 오류를 내지 않고, string의 끝값 까지를 return해준다.

s = "abcd"
print(s[0:10000]) # abcd

허나 자바는 index를 넘어가면 오류를 낸다.

String s = "abcd";
System.out.println(s.substring(0,6)) // Error

이 문제에서 제대로 된 범위값은 s.length()-1 까지이다.

s.length() 에 -1을 해주어야 한다.