[LeetCode 練習] 5. Longest Palindromic Substring(使用python 程式碼)

原本想要至少兩天更新一篇文章，但要寫題目又要寫文章時間真的不夠zzzz。好的回歸正題，今天來解找出字串中最長的回文文字。

1. 題目:

給字串s，找出s中最長的回文文字

2. 範例:

ex1

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

ex2

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

3. 思考1：

這題一開始想到的解法如下:

1. 假設一範圍，此範圍長度的初始值是字串長度。(下圖中的橘框)。

2. 判斷此範圍內文字是否為回文:

3. 文字是回文的話就回傳此文字，結束程式。

4. 文字不是回文的話就縮小範圍，並繼續2.~4.步驟。

以 ex1為例，列出程式的執行步驟，如下圖所述:

1. 給定的s字串長度是5，判斷此範圍內文字是否為回文，（也就是判斷babad是否為回文)，判斷後發現不是回文，所以要縮小範圍並繼續程式。

2. 縮小橘框範圍後，要判斷這個範圍的所有可能文字是否為回文，也就是要判斷baba以及 abad是否為回文，判斷後發現都不是，所以要繼續縮小範圍，並找尋是否為回文。

3. 再次縮小橘框範圍，要判斷這個範圍的所有可能文字是否為回文，也就是要判斷bab, aba, bad是否為回文，發現bab是回文，所以之後不用繼續找，直接回傳此文字並結束程式。(因由長度大到小，長度大已經找到回文文字，就不用繼續往下找)

以上這個作法，簡單的說就是找出字串的所有可能，並判斷是否為回文，是回文的話就返回那個回文的文字，並且不用繼續往下找。

此程式的時間複雜度大約是 n³ ，因為最差的情況：

1. 範圍不斷縮小，執行次數每次加1，1, 2,3 , … n，依照等差級數公式(首相加末項乘項數除2)，可算出時間複雜度為 (1 + n) * n // 2 ~ n²。
2. 然後判斷回文， 需要一個for迴圈判斷左右是否相等，時間複雜度為n

因此兩個部分相乘，時間複雜度就是 n³左右。使用leetcode跑測試，三次下來都只落後10%的速度。

4. 思考2：

我們可以換個方式想，把字串每個文字位置去看他的左邊與右邊是否相同，若左邊與右邊相同，那就是回文了。

1. 以上圖為例，我們建立一個範圍(上圖藍框)，範圍一開始從中間的index(這裡命名為center)開始，判斷這個位置的左右文字是否相同。判斷後發現這個位置，也就是b的左右都是a，是回文，可以將此回文，也就是aba存入目前最長的回文變數max_palindromic 中，並擴大範圍，且中心位置不動。

2. 擴大範圍後，繼續判斷左右兩邊的文字是否相同，判斷結果發現左右兩邊b及d不相同，不是回文，所以這個位置判斷結束，要前往下一個位置。

…

3. 下一個位置可能是往左或往右，我們都要走過，才能正確判斷每個位置是否為回文的可能性，這裡我們先往左走，更新center位置為原本位置-1，然後繼續1. ~2. 判斷是否為回文的過程。

4. 向左走後，發現這個位置判斷左右兩邊文字相同(如上圖，都是b)，判斷這個文字長度有否大於max_palindromic，沒有大於，所以不用更新max_palindromic，可以繼續擴大範圍，看下一個位置的左右文字是否相同。

5. 如上圖，擴大範圍後，發現已超出邊界，所以左邊的部分已結束，可以往右邊找。

6. 往右邊找，也就是center加1，發現位置左右文字不一樣不是回文，繼續往下一個index走。

7. 到這裡，右邊index已超出範圍，所以右邊也找完了，可以推論出最大的回文是max_palindromic也就是aba(或bab)。

以上是奇數個回文文字的狀況，但也有可能有偶數個回文，所以我們同一個文字也要執行偶數個回文的判斷。

因為沒有中間的文字，我們其實只要比較，左右兩個文字是否相同就可以了，我們一樣先找出中間的index，也就是b這個位置，然後判斷它左邊是否與它文字相同，若相同就是回文，若不同就不是回文，很顯然，a不等於b，所以要繼續往下一個位置判斷。

同樣下一個位置也要往左及往右走，列出所有可能性。往左後兩個ba文字也不相同不是回文。要繼續往左走。

繼續往左走後發現已超出範圍，左邊的尋找已結束，要往右尋找。但這裡就不列出來了，因為這個文字沒有偶數個回文的狀況。

我們再看一個有偶數個回文的狀況，我們來看文字cabba

1. 一開始中間index為2，往左邊找，判斷左邊與右邊是否相等，發現兩個文字不相等，要繼續往左找，但我們知道左邊已經沒有回文了，我們直接當作程式已經跑完，開始往右尋找。

2. 往右走後發現左右兩個文字都是b，因此可以擴大範圍，繼續這個範圍外的兩個文字是否相同。

3. 發現左右兩邊文字都是a，因此可以繼續往下尋找。

4. 再判斷左右位置後，發現右方已超出範圍，因此這個位置結束，判斷此文字長度，也就是abba長度是否大於max_palindromic，是，所以把max_palindromic存為abba，然後繼續往右移動，繼續看下一位置是否為左右相等

如上圖，下一位置，左右不相等，因此繼續往下移動。

如上圖，移動後發現已超出範圍，因此最大的回文是abba。

這個程式的時間複雜度，因為只要loop through 文字長度n，以及每個文字往左往右最大的可能性 ~n ，所以時間複雜度大約時n²，用leetcode跑，發現這個寫法速度能贏96%其他人的程式。

5. Python程式碼:

思考1的寫法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s_len = len(s)
        return self.cal_longest_palindromic(s,s_len,s_len)


    def cal_longest_palindromic(self,s,s_len, now_len):
        for i in range((s_len - now_len) + 1): # 1. 列出範圍內的所有可能文字check_str
            check_str = s[i:i+now_len]
            palindromic = self.get_palindromic_or_false(check_str) # 2. 判斷check_str是否為回文。

            if palindromic: # 3. 是回文的話就回傳該回文文字並結束程式。
                return palindromic

        return self.cal_longest_palindromic(s,s_len, now_len - 1) # 4. 不是回文的話就縮小範圍，並繼續找範圍內所有可能的文字是否為回文。


    def get_palindromic_or_false(self, check_str): # 判斷輸入的文字是否為回文
        chk_len = len(check_str)
        chk_half_len = (chk_len // 2)
        for i in range(chk_half_len):
            if check_str[i] != check_str[chk_len - 1 - i]:
                return False
        else:
            return check_str

思考2的寫法

class Solution:
    max_saved_str = ''

    def longestPalindrome(self, s: str) -> str:
        half_idx = len(s) // 2
        last_idx = len(s) - 1
        first_idx = 0
        self.max_saved_str = s[half_idx]

        self.travel_s(s, half_idx, first_idx, last_idx, -1, False) # 1. 判斷奇數狀況，往左移度
        self.travel_s(s, half_idx, first_idx, last_idx, 1, False)  # 2. 判斷奇數狀況，往右移度
        self.travel_s(s, half_idx, first_idx, last_idx, -1, True)  # 3. 判斷偶數狀況，往左移度
        self.travel_s(s, half_idx, first_idx, last_idx, 1, True)   # 4. 判斷偶數狀況，往右移度


        return self.max_saved_str # 5. 回傳最大回文的文字。

    def travel_s(self, s, half_idx, first_idx, last_idx, move_pos, is_even):
        center = half_idx # 1. 中心index
        left_travel_idx, right_travel_idx = self.get_left_right_travel_idx(is_even,center) # 2. 取得左邊與右邊index(會依據奇數與偶數，取得的index會不同)
        saved_str = self.get_reset_save_str(is_even,s,center) # 3. 取得初始文字(會依據奇數與偶數，取得的初始文字會不同)

        while left_travel_idx >= first_idx and right_travel_idx <= last_idx: # 4. 當在邊界內就繼續執行程式。
            left,right = s[left_travel_idx], s[right_travel_idx] 
            if left == right: # 5. 如果左邊文字等於右邊文字，擴大範圍，繼續尋找
                saved_str = left + saved_str + right
                left_travel_idx -= 1
                right_travel_idx += 1

                if len(saved_str) > len(self.max_saved_str): # 6. 如果新文字長度大於max_saved_str，把max_saved_str存成新文字
                    self.max_saved_str = saved_str
            else: # 7. 如果左右邊文字不同，移動中心點，移動左右邊index及將saved_str改為初始值
                center += move_pos
                left_travel_idx, right_travel_idx = self.get_left_right_travel_idx(is_even,center)
                saved_str = self.get_reset_save_str(is_even,s,center)
                continue

    def get_reset_save_str(self, is_even, s, center):
        if is_even: # 偶數時，初始文字為空值
            return ''
        else: # 奇數時，初始文字目前位置的文字
            return s[center]

    def get_left_right_travel_idx(self, is_even, center):
        if is_even: # 偶數時，左右index分別為center-1 及center
            left_travel_idx,right_travel_idx = center - 1, center
        else: # 奇數時，左右index分別為center -1 與center +1
            left_travel_idx,right_travel_idx = center - 1, center + 1
        return (left_travel_idx,right_travel_idx)