Leetcode 647. Palindromic Substrings (Python)

Related Topic

Dynamic-Programming.

Description

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Sample I/O

Example 1

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

## Note: The input string length won’t exceed 1000.

Methodology

This question can be solved by Dynamic Programming. It is similar with question 5. Longest Palindromic Substring. However there are various way to implement DP.

To find palindromic substring, we need to know the start index and end index for each substring. The start index and end index will range the substring as outter boundary. If the start index and end index are same, then we go inner of the boundary by moving start and end index 1 cell inner until the start and end are overlaping or start’s next is end.

Find the base case:

If there is 1 character, then there is 1 palindromic substring. If there are 2 character, then start and end character are same.

dp[start_index][end_index]=1, when there is 1 character

Find the pattern:

We will check start from substring contain 1 character to substring contain n character. For each check we use count to keep adding the number of palindromic substring. Every time we set the first element of this substring as start and last element of this substring as end. We compare the start and end if they are same then we compare start’s next element with end’s previous element, until start and end are overlaping. When they are overlaped, we get the count + previous count

Answer:

Return the count as answer

Code

def countSubstrings(self, s: str) -> int:
        count = 0
        N = len(s)
        dp = [[False] * N for _ in range(N)]
        for l in range(1, N + 1): #each possible length when the string length is l
            for start in range(N - l + 1): #outer
                end = start+l-1
                if l == 1 or (l == 2 and s[start] == s[end]) or (l >= 3 and s[start] == s[end] and dp[start + 1][end - 1]):#dp
                    dp[start][end] = True
                    count += 1
        return count

BigO

Create dp list will cost O(n^2) and iterate the dp will cost (n^2/2) in total will be O(n^2*2/3)