Leetcode刷題-字符串

字符串其實可以看成是字符組成的數組，在leetcode中一般會有以下幾種題型：

不同的字符串題方法也不同，下面具體介紹了5個涉及字符串題的解題思路和python解決方案

尤其最後一題尋找最長回文子串問題中，給出了全新的動態規劃思路，效率僅次於Manacher算法

520. 檢測大寫字母

難度：簡單

給定一個單詞，你需要判斷單詞的大寫使用是否正確。

我們定義，在以下情況時，單詞的大寫用法是正確的：

單詞中所有字母都不是大寫，比如"leetcode"。如果單詞不只含有一個字母，只有首字母大寫， 比如 "Google"。

否則，我們定義這個單詞沒有正確使用大寫字母。

示例 1:

輸入: "USA"
輸出: True
示例 2:
輸入: "FlaG"
輸出: False
注意: 輸入是由大寫和小寫拉丁字母組成的非空單詞。
思路1
根據字母的ASCII碼來區分大小寫，然後判斷前兩個數是否都為大寫字母，如果是，那麼從之後的字母也必須都是大寫，如果不是，從第二個字母開始之後的所有字母必須為小寫字母，如果滿足上面兩個其中一種，返回True，反之如果上面兩種都不滿足則返回False
時間複雜度：
代碼
class Solution:
    def detectCapitalUse(self, word: str) -> bool:
        if len(word) <= 1:
            return True
        if ord(word[0]) < 95 and ord(word[1]) < 95:
            for i in range(2, len(word)):
                if ord(word[i]) > 95:
                    return False
        else:
            for i in range(1, len(word)):
                if ord(word[i]) < 95:
                    return False
        return True
思路2
使用python自帶內置函數upper(), lower(), title()

方法描述1islower()如果字符串中包含至少一個區分大小寫的字符，並且所有這些(區分大小寫的)字符都是小寫，則返回 True，否則返回 False2istitle()如果字符串是標題化的（所有單詞都是以大寫開始，其餘字母均為小寫），則返回 True，否則返回 False3isupper()如果字符串中包含至少一個區分大小寫的字符，並且所有這些(區分大小寫的)字符都是大寫，則返回 True，否則返回 False代碼
class Solution:
    def detectCapitalUse(self, word: str) -> bool:
        return word.isupper() or word.islower() or word.istitle()
680. 驗證回文字符串 Ⅱ
難度：簡單
給定一個非空字符串 s，最多刪除一個字符。判斷是否能成為回文字符串。
示例 1:
輸入: "aba"
輸出: True
示例 2:
輸入: "abca"
輸出: True
解釋: 你可以刪除c字符。
注意:
字符串只包含從 a-z 的小寫字母。字符串的最大長度是50000。思路
雙指針+貪心算法
定義左右兩指針分別指向字符串開頭和結尾，然後比較所指的字符是否相等，如果不相等，那麼肯定就需要刪除一個字符，由於題目要求是最多刪除一個字符，那麼按理說如果刪除後剩下的是回文字符串的話，那麼就返回True，否則False. 因為有兩種刪除方法，那就分別判斷兩種情況，任何一個情況滿足就返回True，否則False.如果相等，那麼左右兩指針分別靠近一步，也就是left++，right--，之後進行下一輪的判定，直到左右兩指針相遇，返回True
時間複雜度：
代碼
class Solution:
    def validPalindrome(self, s: str) -> bool:
        def isPalidrome(s: str):
            l = 0
            r = len(s)-1
            while l < r:
                if s[l] != s[r]:
                    return False
                else:
                    l += 1
                    r -= 1
            return True

        left = 0
        right = len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return isPalidrome(s[left:right]) or isPalidrome(s[left + 1:right + 1])
            else:
                left += 1
                right -= 1
        return True
12. 整數轉羅馬數字
難度：中等
羅馬數字包含以下七種字符：I， V， X， L，C，D 和 M。
字符          數值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 羅馬數字 2 寫做 II ，即為兩個並列的 1。12 寫做 XII ，即為 X + II 。27 寫做 XXVII, 即為 XX + V + II 。
通常情況下，羅馬數字中小的數字在大的數字的右邊。但也存在特例，例如 4 不寫做 IIII，而是 IV。數字 1 在數字 5 的左邊，所表示的數等於大數 5 減小數 1 得到的數值 4 。同樣地，數字 9 表示為 IX。這個特殊的規則只適用於以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊，來表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左邊，來表示 400 和 900。
給定一個整數，將其轉為羅馬數字。輸入確保在 1 到 3999 的範圍內。
示例 1:
輸入: 3
輸出: "III"
示例 2:
輸入: 4
輸出: "IV"
示例 3:
輸入: 9
輸出: "IX"
示例 4:
輸入: 58
輸出: "LVIII"
解釋: L = 50, V = 5, III = 3.
示例 5:
輸入: 1994
輸出: "MCMXCIV"
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
思路
直接將對應的關係放進哈希表中或數組中即可，然後對當前數不斷取餘，判斷餘數處於哪個區間，並加上對應的羅馬字符即可。
時間複雜度：
代碼
class Solution:
    def intToRoman(self, num: int) -> str:
        dic = {1000: "M", 500: "D", 100: "C", 50: "L", 10: "X", 5: "V", 1: "I"}
        bound = [1000, 500, 100, 50, 10, 5, 1]
        res = ""
        for i in range(0, 7, 2):
            if num >= bound[i]:
                n, num = divmod(num, bound[i])
                if n >= 5:
                    if n == 9:
                        res += dic[bound[i]]+dic[bound[i-2]]
                    else:
                        res += dic[bound[i-1]]+(n-5)*dic[bound[i]]
                else:
                    if n == 4:
                        res += dic[bound[i]] + dic[bound[i - 1]]
                    else:
                        res += n * dic[bound[i]]
            else:
                continue
        return res

93. 復原IP位址
難度：中等
給定一個只包含數字的字符串，復原它並返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四個整數（每個整數位於 0 到 255 之間組成，且不能含有前導 0），整數之間用 '.'分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 無效的 IP 地址。
示例 1：
輸入：s = "25525511135"
輸出：["255.255.11.135","255.255.111.35"]
示例 2：
輸入：s = "0000"
輸出：["0.0.0.0"]
示例 3：
輸入：s = "1111"
輸出：["1.1.1.1"]
示例 4：
輸入：s = "010010"
輸出：["0.10.0.10","0.100.1.0"]
示例 5：
輸入：s = "101023"
輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
思路
這題其實可以看成，用三個點將一個字符串切分為4部分，每個部分滿足在0到255之間，且不能有前導0（比如「012」不能作為ip地址的一部分），那麼其實就是個排列組合當中的組合題，並做適當剪枝，解組合題常用的方法就是回溯法
回溯法：
回溯過程即每次都在前1-3個字符之後加上「.」，然後將這些字符存入中間變量comb中，然後取剩餘的字符串進入下一輪迴溯，本輪循環過後需要進行回置，即將中間變量回置為添加上面字符和"."之前的狀態
回溯出口有以下幾種：
當4個點（第四個點加到了最後）都加完時，且所有字符串中的字符都存入了中間變量comb，則將這個comb存入到最後結果res中如果當前字符串的長度太大，以至於加入剩餘的"."會使得某個部分長度大於3，那麼直接退出回溯如果當前字符串的長度太小，以至於加入剩餘的"."會使得某個部分長度等於0，那麼直接退出回溯代碼
class Solution:
    def restoreIpAddresses(self, s: str) -> [str]:
        res = list()

        def backtrack(s: str, split: int, comb: str):
            if split < 0:
                if len(s) == 0:
                    res.append(comb[:-1])
                return
            if len(s) > (split+1)*3:
                return
            elif len(s) <= split:
                return
            else:
                right = len(s) - split+1 if len(s) - split+1 < 4 else 4
                if s[0] == "0":
                    right = 2
                for i in range(1, right):
                    if int(s[:i]) > 255:
                        continue
                    comb += s[:i] + "."
                    backtrack(s=s[i:], split=split - 1, comb=comb)
                    comb = comb[:-(i + 1)]

        backtrack(s, 3, "")
        return res
5. 最長回文子串
難度：中等
給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
示例 2：
輸入: "cbbd"
輸出: "bb"
思路1：暴力法
從頭開始遍歷，按如下方式尋找以當前字母
從字符串尾開始，從後往前遍歷字符串中的字母$\alpha_j,\ i判斷
噹噹前最大字符串長度大於等於當前遍歷的字母到結尾的長度時，跳出循環，並返回最大字符串長度所對應的字符串
時間複雜度：
結果：超時
代碼（兩個for循環）：
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def isPalindrome(s: str) -> bool:
            left = 0
            right = len(s)-1
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        max_len = 0
        for i in range(len(s)):
            if max_len >= len(s) - i:
                break
            for j in reversed(range(len(s))):
                if isPalindrome(s[i:j + 1]):
                    if max_len < j - i + 1:
                        max_len = j - i + 1
                        res = s[i:j + 1]
                    break
        return res
思路2：中心擴展算法
中心擴展算法其實跟上面暴力法思路是一樣的，它也是先從前往後遍歷字符串中的字母，不同的是，它並不是以當前字母為開頭來尋找最長的回文子串，而是向兩邊擴展來尋找最長的回文子串。這樣尋找的優點在於，它擴展得到的子串就是回文子串而不需要在進行判斷。不過這裡的擴展有兩種情況：
以當前遍歷的字母
至於上面還有一個情況是以
從前往後遍歷過程中，當發現當前最長回文子串的長度的一半（也就是臂長，下面會講到）大於等於當前遍歷字母到結尾的長度時，停止遍歷，輸出前面得到的最長回文子串。
時間複雜度：
代碼
class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        遍歷字符串，從當前字符串往兩邊擴展，找到最長的字符串並記錄
        方法：定義一個擴展函數，從當前遍歷到的字母處開始，1種是以當前字母為中心，向兩邊擴展，
        另外一種是以當前字母後後一個字母整體為中心向兩邊擴展，如果發現擴展的兩端字母不等
        則停止。兩種擴展方法分別對應奇數長度和偶數長度回文字符串。
          函數返回當前字母兩種擴展最長的回文子串長度和對應的回文子串
        時間複雜度：O(n^2) 空間複雜度：O(1)
        """
        def expand(idx: int, s: str):
            len1 = 1
            left, right = idx - 1, idx + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                len1 += 2
            len2 = 0
            left, right = idx, idx + 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                len2 += 2
            if len1 >= len2:
                return [len1, s[idx - len1 // 2:idx + len1 // 2 + 1]]
            else:
                return [len2, s[idx - len2 // 2 + 1:idx + len2 // 2 + 1]]
            
        max_len = 0
        for i in range(len(s)):
            if max_len // 2 >= len(s) - i:
                break
            l, ch = expand(i, s)
            if max_len < l:
                max_len = l
                res = ch
        return res
leetcode官方題解上代碼更為簡潔，也是同樣思路，只不過在擴展時並沒有存儲得到的最長回文子串的長度，而是記錄擴展得到的最左和最右兩個字母的index
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]
思路3：動態規劃leetcode上面的官方題解
我們用
那麼我們可以寫出狀態轉移方程：
明顯發現，上面的狀態轉移方程只適用於j-i>=3這種情況，那麼我們還要考慮小於3的情況：
時間複雜度：
結果：超時
代碼
class Solution:
    def longestPalindrome(self, s: str) -> str:
        len_s = len(s)
        dp = [[False] * len_s for _ in range(len_s)]
        ans = ""
        #子序列從長度為0開始遍歷
        for len_subseq in range(len_s):
            #子序列首字母i
            for i in range(len_s):
                #子序列尾字母j
                j = i+len_subseq
                if j >= len_s:
                    break
                if len_subseq == 0:
                    dp[i][j] = True
                elif len_subseq == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1]) & (s[i] == s[j])
                if dp[i][j] & (len_subseq+1>len(ans)):
                    ans = s[i:j+1]
        return ans
動態規劃+分類討論
這裡我們用dp存儲以每個字母結尾的最長回文子串的長度，也就是說dp[i]表示以s[i]結尾的最長回文子串的長度。
如果：
反證法證明：對於一段字符串
假設：
那麼在
否則：
之所以從
令這麼一段字符串現在我們遍歷到了第i+1個元素處，即
我們的推斷是，當
假設在

時間複雜度：
代碼
class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [1]
        max_len = 1
        end_index = 0
        for i in range(1, len(s)):
            if (i - dp[i - 1] - 1 >= 0) & (s[i] == s[i - dp[i - 1] - 1]):
                dp.append(dp[i - 1] + 2)
            else:
                #從i-dp[i-1]個字母處從左往右遍歷
                j = i - dp[i - 1]
                while j<=i:
                    if self.isPalindrome(s[j:i+1]):
                        dp.append(i-j+1)
                        break
                    j += 1
            if dp[i] > max_len:
                max_len = dp[i]
                end_index = i
        return s[end_index - max_len + 1: end_index + 1]
    #判斷是否為回文子串
    def isPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True
思路4：Manacher 算法預處理：擴展字符串，使其最長回文子串的長度始終為奇數
算法分析
動態規劃與中心擴展相結合：
定義一個數組p, p[i]表示以字符串中第i個字符向左右兩邊擴展的最大回文子串長度
定義兩個變量：
maxRight：記錄前面遍歷的回文子串能夠觸及到的最右邊字母的下標center：上面maxRight對應的回文子串的中心字母下標
下面我們開始對字符串從前往後進行遍歷，並不斷更新p，更新時候有以下情況：
當p[mirror] < maxRight-i 時，有p[i] = p[mirror] < maxRight-i。當p[mirror] == maxRight-i 時，有p[i] >= maxRight-i，所以需要從maxRight處開始進行中心擴展方法。當p[mirror] > maxRight-i 時，有p[i] = maxRight-i。
代碼
class Solution:
    def expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return (right - left - 2) // 2

    def longestPalindrome(self, s: str) -> str:
        end, start = -1, 0
        s = '#' + '#'.join(list(s)) + '#'
        arm_len = []
        right = -1
        j = -1
        for i in range(len(s)):
            if right >= i:
                i_sym = 2 * j - i
                min_arm_len = min(arm_len[i_sym], right - i)
                cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
            else:
                cur_arm_len = self.expand(s, i, i)
            arm_len.append(cur_arm_len)
            if i + cur_arm_len > right:
                j = i
                right = i + cur_arm_len
            if 2 * cur_arm_len + 1 > end - start:
                start = i - cur_arm_len
                end = i + cur_arm_len
        return s[start+1:end+1:2]
參考文獻leetcode中文官網：https://leetcode-cn.com/