[LeetCode][Java] Longest Palindromic Substring
유명한 알고리즘 문제 팔린드롬 문제입니다! 테스트에선 본 적은 없지만 여러 알고리즘 사이트에 기본적으로 나오는 문제에요. 알아두면 좋은 문제라 생각합니다.
문제
Given a string s, return the longest palindromic substring in s.
제한사항
- 1 <= s.length <= 1000
s
consist of only digits and English letters.
접근
Given a string s, return the longest palindromic substring in s.
s
consist of only digits and English letters.팔린드롬Palindrome
이 무엇인지 알면 이해하는데 쉽습니다. 보통 이걸 알고 있다는 건 이미 문제를 풀어봤다는 이야기이기도 하지만요 ㅎㅎ
팔린드롬Palindrome
은 문자 배치가 거울처럼 미러링된, 대칭된 문자열입니다. 예제로 설명드리자면,
- "aba" O
- "a" O
- "adad" X
- "aaa" O
- "aa" O
짝수면 맞는 짝 위치끼리 비교를 하고, 홀수인 경우 짝을 이룰 수 없는 정가운데 문자를 제외하고 비교합니다. 이정도면 팔린드롬에 대한 이해가 충분히 될거라 봅니다.
저는 투 포인터Two Pointer
개념을 사용해 문제를 풀었습니다. left
값을 0, right
값을 문자열 마지막 인덱스로 주고 substring
을 통해 팔린드롬Palindrome
인지 확인을 하고 맞으면 찾은 답보다 길면 답에 초기화하고 left
를 증가시켜 기준점을 새로 하고 substring
을 구성해 답을 찾고, 아니면 right
를 빼주는 식으로 전개했어요.
답안
class Solution{
public boolean IsPalindrome(String s){
int left = 0, right = s.length() - 1;
while(left < right){
if(s.charAt(left) != s.charAt(right))
return false;
++left;
--right;
}
return true;
}
public String longestPalindrome(String s) {
if(s.length() <= 1)
return s;
String answer = "";
int left = 0, right = s.length() - 1;
while(left <= right){
String subStr = s.substring(left, right + 1);
if(answer.length() >= subStr.length()) {
++left;
right = s.length() - 1;
continue;
}
if(IsPalindrome(subStr)){
answer = subStr;
++left;
right = s.length() - 1;
}
else{
--right;
}
}
return answer;
}
}
Author And Source
이 문제에 관하여([LeetCode][Java] Longest Palindromic Substring), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@redgem92/LeetCodeJava-Longest-Palindromic-Substring저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)