主題
難度: Medium
===========================================================================
給予一個字串”s”,返回最長的回文字串.
===========================================================================
條件限制:1 ≤ s.length ≤ 1000s由數字與英文組成
===========================================================================
測資1:
Input: s = “babad”
Output: “bab”
注意!“aba”也是有效的答案
測資2:
Input: s = “cbbd”
Output: “bb”
測資3:
Input: s = “a”
Output: “a”
測資4:
Input: s = “ac”
Output: “a”
注意!”c”也是有效的答案
===========================================================================
解題思路:
1.此題為Dynamic Programming,
採用2維List的方式進行解題,將字串展成2維的表格,
由row與colum指標分別由2個方向進行搜索,
我們定義2維的表格Palindromic[i][j],儲存回文的結果,
i為row方向的index, j為colum方向的index
| Index | j | 0 | 1 | 2 | 3 | 4 |
| i | Char | a | b | a | b | c |
| 0 | a | |||||
| 1 | b | |||||
| 2 | a | |||||
| 3 | b | |||||
| 4 | c |
2.若是遇到有回文的組合,則在該組合上標上True,
當指標同時重疊於同一字元,也視為回文,
因此我們可在Palindromic[i][i]上的位置皆標上True.
| Index | j | 0 | 1 | 2 | 3 | 4 |
| i | Char | a | b | a | b | c |
| 0 | a | True | ||||
| 1 | b | True | ||||
| 2 | a | True | ||||
| 3 | b | True | ||||
| 4 | c | True |
3.我們來認識回文的定理:
有一組文字”a…a”要判斷是否為回文,
若“…”中的文字為回文,則”a…a”必為回文
因此當出現s[i]==s[j]時,要判斷內部字串s[i+1]與s[j-1]的位置是否為回文,
以”ababc”當範例,當i=0與j=2的時候,搜尋到的字串為”a…a”,
此時s[i]==s[j]=”a”,因此要去判斷s[i+1]與s[j-1]的位置是否為回文,
在s[i+1]與s[j-1]的位置為i=1與j=1,在先前Palindromic[1][1]已被標示為True,此格為“b”
依照定理可確定s[i]與s[j]間的字串必為回文.
| Index | j | 0 | 1 | 2 | 3 | 4 |
| i | Char | a | b | a | b | c |
| 0 | a | True | True | |||
| 1 | b | True | ||||
| 2 | a | True | ||||
| 3 | b | True | ||||
| 4 | c | True |
4.為了要確保Palindromic[i][j]在左下方的位置Palindromic[i+1][j-1],
總是有值可以取用,因此採用『由上而下由左而右』進行搜索.
(『由右而左由下而上』或『由下而上由左而右』,進行搜索也是可行的)
| Index | j | 0 | 1 | 2 | 3 | 4 |
| i | Char | a | b | a | b | c |
| 0 | a | True | ↓ | ↓ | ↓ | ↓ |
| 1 | b | True | ↓ | ↓ | ↓ | |
| 2 | a | True | ↓ | ↓ | ||
| 3 | b | True | ↓ | |||
| 4 | c | True |
5.另外考量到在偶數回文的狀況,例如:”abba”, s[1]==s[2]=b
但在Palindromic[1][2]的左下角Palindromic[2][1]卻沒有數值,
為了修正此狀況,因此新增一條件:
在s[i]==s[j]時,若j-i == 1則也視為回文,表格在該位置標記為True.
===========================================================================
解題:程式已按上述的步驟進行標註.
class Solution:
def longestPalindrome(self, s: str) -> str:
sLength=len(s);
Palindromic=[[False]*sLength for _ in range(sLength)]; #步驟1:建立回文的2維表格
for i in range(sLength): #步驟2:先將左右指標在相同位置(指向同一字符)視為回文
Palindromic[i][i]=True;
PalindromicLength=PalindromicStartIndex=0;
MaxPalindromicLength=1;
for j in range(sLength): #步驟4:由上往下由左而右進行搜索
for i in range(j+1):
if ( i == sLength-1 and j == sLength-1 ) or ( s[i] == s[j] and ( Palindromic[i+1][j-1] or j-i == 1 )): #步驟3:碰到相同字元要進行回文檢查, 檢查該格左下角的格子是否為回文
#步驟5:j與i差1時左下角無東西,考量到雙數對會出錯, ex:abba "bb"的判斷會出錯
Palindromic[i][j]=True;
PalindromicLength=j-i+1; #計算目前回文的長度
if PalindromicLength>=MaxPalindromicLength: #判斷目前的回文是否為最大長度長度
PalindromicStartIndex=i;
MaxPalindromicLength=PalindromicLength;
return s[PalindromicStartIndex:PalindromicStartIndex+MaxPalindromicLength]
===========================================================================
本文轉載自本帥的Medium部落格:跳蚤的蛋蛋跳蚤蛋
達人
