Palindromic String¶
LeetCode 5. Longest Palindromic Substring¶
Solutions:
class Solution(object):
def longestPalindrome_0(self, s):
"""
:type s: str
:rtype: str
"""
if s == s[::-1]:
return s
# len of palindromic substring starting from
dp = [[False for i in range(len(s) + 1)] for j in range(len(s) + 1)]
start = 0
maxlen = 0
for i in range(len(s), 0, -1): # [N, ..., 1]
for j in range(i, len(s) + 1):
if i == j or i + 1 == j:
dp[i][j] = s[i - 1] == s[j - 1]
else:
dp[i][j] = s[i - 1] == s[j - 1] and dp[i + 1][j - 1]
if dp[i][j] and j - i > maxlen:
maxlen = j - i
start = i - 1
return s[start: start + maxlen + 1]
def longestPalindrome(self, s):
res = ""
for i in xrange(len(s)):
# odd case, like "aba"
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even case, like "abba"
tmp = self.helper(s, i, i + 1)
if len(tmp) > len(res):
res = tmp
return res
# get the longest palindrome, l, r are the middle indexes
# from inner to outer
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1;
r += 1
return s[l + 1:r]
LeetCode 647. Palindromic Substrings¶
My first thought is to use permutation
Solutions:
class Solution(object):
def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
# when think up the DP solution, DP will stand for True/False instead of number of palindrome.
# It's because when you set it to #, it's very hard to build the relationship between N and N-1.
if len(s) == 0:
return 0
N = len(s)
dp = [[1 if i == j else 0 for i in range(N + 1)] for j in range(N + 1)]
count = 0
for i in range(1, N+1):
for j in range(i, 0, -1):
# since we need next pos's info to decide current info, we can't use ascending order, we need
# descending order
if i == j:
dp[i][j] = 1
else:
dp[i][j] = 1 if (s[i - 1] == s[j - 1]) and (dp[i - 1][j + 1] or j+1==i) else 0
print dp
if dp[i][j]:
count += 1
return count