LeetCode | 0647. Palindromic Substrings回文子列【Medium】【Python】【中心拡張】【動的計画】

LeetCode 0647. Palindromic Substrings回文子列【Medium】【Python】【中心拡張】【動的計画】
Problem
LeetCode
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.
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.

に質問
スナップ
文字列を指定すると、この文字列に何個の返信サブ列があるかを計算します.
異なる開始位置または終了位置を持つサブストリングは、同じ文字で構成されていても異なるサブストリングとみなされます.
例1:

  ："abc"
  ：3
  ：      : "a", "b", "c"

例2:

  ："aaa"
  ：6
  ：6     : "a", "a", "a", "aa", "aa", "aaa"

ヒント:

入力文字列の長さは1000を超えません.

構想
解法一:中心拡張

            ，          ，             。
                ，        ，          。

例n=4:
番号i
回文中心左開始位置li
回文中心右開始位置ri
0
0
0
1
0
1
2
1
1
3
1
2
4
2
2
5
2
3
6
3
3

    ，    n         2n-1      [li,ri]，  li = i/2，ri = li + (i mod 2)。
     0   2n-2，           。

時間複雑度:O(n^2)
Python 3コード

class Solution:
    def countSubstrings(self, s: str) -> int:
        # solution one:     
        n = len(s)
        ans = 0
        for i in range(2 * n - 1):
            left, right = int(i / 2), int(i / 2) + i % 2
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1 #    
                right += 1 #    
                ans += 1
        return ans

解法二:動的計画

    dp[i...j]       ，   ，dp[i][j] = true，    ，dp[i][j] = false

      ：dp[i][j] = dp[i + 1][j - 1]

base case：                

           ：
	  ：
		j - i == 1：       2
		j - i != 1：        ，    substring        
	  ：
		      

時間複雑度:O(n^2)
Python 3コード

class Solution:
    def countSubstrings(self, s: str) -> int:
        # solution two:     
        if s is None or s == "":
            return 0
        
        n = len(s)
        dp = [[False for _ in range(n)] for _ in range(n)]
        res = len(s)

        for i in range(n):
            # base case
            dp[i][i] = True
        #                
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    # i   j   ，        2
                    if j - i == 1:
                        dp[i][j] = True
                    #       ，    substring        
                    else:
                        dp[i][j] =  dp[i + 1][j - 1]
                #           
                else:
                    dp[i][j] = False
                if dp[i][j]:
                    res += 1
        return res

GitHubリンク
Python
リファレンス
回文子列
647.回文サブストリング動的計画方式の解