알고리즘 문제/Leetcode
[Leetcode] 516. Longest Palindromic Subsequence
햄과함께
2023. 4. 14. 20:55
320x100
문제 : https://leetcode.com/problems/longest-palindromic-subsequence/description/
주어진 문자열 s에서 가장 긴 회문 부분 수열의 길이를 찾으세요.
부분 수열이란 다른 수열에서 일부 또는 전혀 없애지 않고 남은 원소들의 순서를 변경하지 않고 유도할 수 있는 수열입니다.
DP로 풀 수 있습니다.
dp[i][j] = s[i~j] 의 부분 수열의 가장 긴 펠린드롬 길이.
dp[i][j] = dp[i+1][j-1] + 2 (s[i] == s[j])
= max(dp[i+1][j], dp[i][j-1]) (s[i] != s[j])점화식은 위와 같습니다.
만약, 문자열의 가장 앞과 뒤의 문자가 같다면 문자열의 가장 앞, 뒤 문자를 부분 수열에 포함하여 길이는 + 2가 되고 그 사이에 있는 문자열의 가장 긴 펠린드롬의 부분 수열 길이를 더합니다. 그래서 s[i] == s[j] 인 경우, dp[i+1][j-1] + 2.
ex) a~~~a 라면 가장 앞, 뒤 문자가 a로 동일하여 이를 부분 수열에 추가한 뒤 그 사이에 있는 문자열들 중 다시 최대길이를 구합니다.
문자열의 가장 앞과 뒤의 문자가 다르다면 문자열의 가장 앞 혹은 가장 뒤의 문자를 하나 제거한 경우의 부분 문자열에서 다시 정답을 구합니다. 이 둘 중 더 긴게 정답이 됩니다. 그래서 s[i] != s[j] 인 경우, dp[i+1][j] (가장 앞 제거), dp[i][j-1] (가장 뒤 제거) 중 더 큰게 최대길이가 됩니다.
시간, 공간 복잡도는 O(N^2).
320x100