목록LongestPalindromicSubstring (1)

개발자가 되고 싶은 준개발자

[LeetCode] 5. Longest Palindromic Substring 풀이 및 코드

동적 프로그래밍 카테고리에 있는 문제로 가장 긴 앞뒤가 같은 문자열을 찾는 문제이다. 풀이 동적 프로그래밍으로 문제를 풀기 위해서는 계산한 결과를 저장하여 다음에 '재사용'하여야 한다. Palindrome은 앞뒤가 같은 문자열로, 전체가 palindrome이면 부분도 palindrome이다. "abcba"로 예를 들어보자. "abcba"가 palindrome이면, "bcb", "c"도 모두 palindrome이다. 따라서 작은 문제부터 풀고, 큰 문제는 +𝛂만 추가로 확인하면 된다. 우선 가장 가운데의 "c"가 palindrome인지 확인하고, 맞다면 그 양 옆의 문자인 "b"를 추가로 확인한다. 양 옆의 문자가 같다면, 이 또한 palindrome이다. 그러면 다시 그 양 옆의 문자를 확인하는 식으로 ..
알고리즘 공부/LeetCode 2020. 9. 18. 20:51
이전 Prev 1 Next 다음