To solve this problem, we need to find the length of the longest palindromic subsequence (LPS) in a given string. A palindromic subsequence is a sequence that reads the same forwards and backwards, and it does not need to be contiguous.
Approach
The approach to solve this problem uses dynamic programming (DP) to efficiently compute the LPS length. The key idea is to build a DP table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i..j] (inclusive).
- DP Table Initialization: Create a 2D DP table of size
n x n(wherenis the length of the string) initialized to zero. Each diagonal elementdp[i][i]is set to 1 because a single character is a palindrome of length 1. - Filling the DP Table: We fill the DP table from the bottom up. For each substring length starting from 2 up to
n, we check if the characters at the ends of the substring are the same. If they are, the LPS length isdp[i+1][j-1] + 2(adding the two matching characters to the LPS of the inner substring). If not, the LPS length is the maximum of the LPS of the substring excluding the left character (dp[i+1][j]) or the substring excluding the right character (dp[i][j-1]).
Solution Code
def longestPalindromeSubseq(s):
n = len(s)
# Correctly initialize DP table with separate rows
dp = [[0] * n for _ in range(n)]
# Single character is a palindrome of length 1
for i in range(n-1, -1, -1):
dp[i][i] = 1
# Check all substrings starting at i and ending at j > i
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
Explanation
- Initialization: The DP table
dpis initialized with[[0] * n for _ in range(n)]to ensure each row is a separate list (avoiding reference issues). - Diagonal Elements: Each
dp[i][i]is set to 1 because a single character is a palindrome. - Filling the Table: For each substring starting at index
iand ending at indexj(wherej > i), we check if the characters atiandjare the same. If they are, we add 2 to the LPS length of the inner substring (dp[i+1][j-1]). If not, we take the maximum LPS length from either the substring excludingi(dp[i+1][j]) or the substring excludingj(dp[i][j-1]). - Result: The value
dp[0][n-1]gives the length of the longest palindromic subsequence in the entire string.
This approach efficiently computes the LPS length with a time complexity of O(n^2) and space complexity of O(n^2), which is optimal for this problem. The space complexity can be optimized to O(n) if needed, but the O(n^2) solution is straightforward and easy to understand.


作者声明:本文包含人工智能生成内容。