【LeetCode】5. Longest Palindromic Substring 解答・解説【Python】

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
1. 解答1：前と後ろから走査して一致する最長文字列を返す
2. 解答2：各文字から左右に広げ、左右が一致する最長文字列を返す
補足・参考・感想

問題

原文

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

1
2

Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000

s consist of only digits and English letters.

内容

文字列sが与えられるので、最長回文文字列を返してください。

※回文とは前から読んでも後ろから読んでも同じ文字であることを指します。

※正しくない可能性があります。

方針

前提

実装のイメージ

➀前後から走査して、一致する最長文字列を返す

②文字列sを左端から順に走査

→各要素を中心として、その左右の文字が一致している限り、左右に広げ続ける。

→限界まで左右に広げた時の文字列を返す

解答

解答1：前と後ろから走査して一致する最長文字列を返す

class Solution:
    def longestPalindrome(self, s):
        #戻り値の変数を用意
        longest_palindrom = ''
        #DPテーブルを用意
        dp = [[0]*len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = True
            longest_palindrom = s[i]
            #print(dp,"dp")
            #print(longest_palindrom,"longest_palindrom")
		
        #文字列sの最後の要素から最初の要素に向かって逆順に処理
        for i in range(len(s)-1,-1,-1):
            #iの位置(後ろから前に処理してきている)から文字列sの長さの分だけ処理
            for j in range(i+1,len(s)):
                #s[i]とs[j]が一致している場合
                if s[i] == s[j]:  
                    #j,iが文字列s内で隣同士、または内側のforの次で処理される場所がTrueの場合
                    if j-i == 1 or dp[i+1][j-1] is True:
                        #今の場所をTrueにする
                        dp[i][j] = True
                        #print(dp)
                        #print(longest_palindrom,"longest_palindrom")
                        #longest_palindromの長さが上回っていれば更新
                        if len(longest_palindrom) < len(s[i:j+1]):
                            longest_palindrom = s[i:j+1]
                
        return longest_palindrom

class Solution:

def longestPalindrome(self, s):

#戻り値の変数を用意

longest_palindrom = ''

#DPテーブルを用意

dp = [[0]*len(s) for _ in range(len(s))]

for i in range(len(s)):

dp[i][i] = True

longest_palindrom = s[i]

#print(dp,"dp")

#print(longest_palindrom,"longest_palindrom")

#文字列sの最後の要素から最初の要素に向かって逆順に処理

for i in range(len(s)-1,-1,-1):

#iの位置(後ろから前に処理してきている)から文字列sの長さの分だけ処理

for j in range(i+1,len(s)):

#s[i]とs[j]が一致している場合

if s[i] == s[j]:

#j,iが文字列s内で隣同士、または内側のforの次で処理される場所がTrueの場合

if j-i == 1 or dp[i+1][j-1] is True:

#今の場所をTrueにする

dp[i][j] = True

#print(dp)

#print(longest_palindrom,"longest_palindrom")

#longest_palindromの長さが上回っていれば更新

if len(longest_palindrom) < len(s[i:j+1]):

longest_palindrom = s[i:j+1]

return longest_palindrom

解答2：各文字から左右に広げ、左右が一致する最長文字列を返す

class Solution:
    def longestPalindrome(self, s):
        #戻り値の変数を用意
        res = ""
        #文字列sの左端から順に処理
        for i in range(len(s)):
            tmp = self.helper(s, i, i)
            #tmpがresよりも大きい場合
            if len(tmp) > len(res):
                #resを更新
                #print(tmp,1)
                res = tmp
            tmp = self.helper(s, i, i+1)
            #print(tmp)
            #tmpがresよりも大きい場合
            if len(tmp) > len(res):
                #resを更新
                #print(tmp,2
                res = tmp
        return res
    
    #文字列sのある要素を中心として左右に広げていく
    def helper(self, s, l, r):
        #lは左端まで、rは右端までで、
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        #while内でl-1,r+1をしているため、l+1:rになる
        return s[l+1:r]

class Solution:

def longestPalindrome(self, s):

#戻り値の変数を用意

res = ""

#文字列sの左端から順に処理

for i in range(len(s)):

tmp = self.helper(s, i, i)

#tmpがresよりも大きい場合

if len(tmp) > len(res):

#resを更新

#print(tmp,1)

res = tmp

tmp = self.helper(s, i, i+1)

#print(tmp)

#tmpがresよりも大きい場合

if len(tmp) > len(res):

#resを更新

#print(tmp,2

res = tmp

return res

#文字列sのある要素を中心として左右に広げていく

def helper(self, s, l, r):

#lは左端まで、rは右端までで、

while l >= 0 and r < len(s) and s[l] == s[r]:

l -= 1; r += 1

#while内でl-1,r+1をしているため、l+1:rになる

return s[l+1:r]

補足・参考・感想

参考

前：12. Integer to Roman

次：6. Zigzag Conversion

LeetCode 解答・解説記事一覧