File tree Expand file tree Collapse file tree
Expand file tree Collapse file tree Original file line number Diff line number Diff line change 1+ """
2+ author: Sanket Kittad
3+ Given a string s, find the longest palindromic subsequence's length in s.
4+ Input: s = "bbbab"
5+ Output: 4
6+ Explanation: One possible longest palindromic subsequence is "bbbb".
7+ Leetcode link: https://leetcode.com/problems/longest-palindromic-subsequence/description/
8+ """
9+
10+
11+ def longest_palindromic_subsequence (input_string : str ) -> int :
12+ """
13+ This function returns the longest palindromic subsequence in a string
14+ >>> longest_palindromic_subsequence("bbbab")
15+ 4
16+ >>> longest_palindromic_subsequence("bbabcbcab")
17+ 7
18+ """
19+ n = len (input_string )
20+ rev = input_string [::- 1 ]
21+ m = len (rev )
22+ dp = [[- 1 ] * (m + 1 ) for i in range (n + 1 )]
23+ for i in range (n + 1 ):
24+ dp [i ][0 ] = 0
25+ for i in range (m + 1 ):
26+ dp [0 ][i ] = 0
27+
28+ # create and initialise dp array
29+ for i in range (1 , n + 1 ):
30+ for j in range (1 , m + 1 ):
31+ # If characters at i and j are the same
32+ # include them in the palindromic subsequence
33+ if input_string [i - 1 ] == rev [j - 1 ]:
34+ dp [i ][j ] = 1 + dp [i - 1 ][j - 1 ]
35+ else :
36+ dp [i ][j ] = max (dp [i - 1 ][j ], dp [i ][j - 1 ])
37+
38+ return dp [n ][m ]
39+
40+
41+ if __name__ == "__main__" :
42+ import doctest
43+
44+ doctest .testmod ()
You can’t perform that action at this time.
0 commit comments