Solution to LeetCode 647 Palindromic Substrings and LeetCode 516 Longest Palindromic Subsequence.
LeetCode 647
Palindromic Substrings (Medium) [link]
1] Brute Force solution. Time complexity O(n^3).
2] Dynamic Programming. Define dp[i][j] as (True of False) whether [i,j] is a palindromic string.
Case1: s[i] != s[j], dp[i][j] = False.
Case2: s[i] == s[j], if i=j, dp[i][j] = True; if i-j = +-1, dp[i][j] = True ; if i-j > 1 or i-j < -1, dp[i][j] = dp[i+1][i-1].
Initialization: dp[i][j] = False.
Because dp[i+1][j-1] is on the left bottom of dp[i][j]， the outer loop is iterating from the bottom to the top, and the inner loop is iterating from the left to the right.
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[False] * len(s) for _ in range(len(s))]
res = 0
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j]:
if j - i <= 1:
res += 1
dp[i][j] = True
elif dp[i+1][j-1]:
res += 1
dp[i][j] = True
return res
LeetCode 516
Longest Palindromic Subsequence (Medium) [link]
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Define dp[i][j] as the longest length of the palindromic subsequence in s[i,j].
Case1: s[i] != s[j], only add s[i] or add s[j] see whether it can form a longer palindromic sequence. Therefore, dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
Case2: s[i] == s[j], dp[i][j] = dp[i + 1][j - 1] + 2.
Initialization: if i=j, then the longest palindromic subsequence is of length 1. dp[i][j]=1. If i!=j, then dp[i][j]=0.
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s)-1, -1, -1):
for j in range(i+1, len(s)):
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][-1]
