Leetcode题解 - 字符串

本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是字符串相关题目题解总结。

[TOC]

5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

解题思路

暴力解决

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
        maxlen = 0
        start = 0
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                if s[i:j] == s[i:j][::-1] and j-i > maxlen:
                    maxlen = j-i
                    start = i
        if maxlen > 0:
            return s[start:start+maxlen]
        return ''

动态规划

动态规划有两个特点：将大问题拆解为小问题，利用之前的计算结果。

例子：”babad”
新建dp二维数组,
$dp[i][j]=1$
时则说明第i到第j为回文子串。

[[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]]

• 首先计算长度为1的子串，必定是回文；
• 然后判断长度为2的子串，根据相等与否判断是否为回文；
• 到长度为3时，就可以利用上次的计算结果：
  • 如果中心对称的短字符串(去掉头尾，此时只有第2个位置的一个字符)是回文，且如果第1和第3个位置相等，则长字符串也是回文；如果第1和第3个位置不相等，则长字符串不是回文；
  • 如果中心对称的短字符串(去掉头尾)不是回文，则长字符串也不是回文；
• 一直遍历到长度最长的字符串。

即当i=j+1时相邻是为长度为2的情况，当i-j > 2时为长度为3的情况，递推式为：
$dp[i][i] = 1$
$dp[j][i] = (s[i] == s[j]) \& (i-j<=2 | dp[j + 1][i - 1])$

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
        dp = [[0]*len(s) for _ in range(len(s))]
        start, end, maxlen = 0, 0, 0
        for i in range(len(s)):
            for j in range(i):
                dp[j][i] = (s[i]==s[j]) & ((i-j<=2) | dp[j+1][i-1])
                if dp[j][i] and maxlen < i-j+1:
                    maxlen = i-j+1
                    start = j
                    end = i
            dp[i][i] = 1
        return s[start:end+1]

Manacher算法

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        if len(s) == 0:
            return ''

        s = self.init(s)
        p = [0] * len(s)
        id = -1 # 记录最右回文子串的中心
        mx = -1
        res = 0
        maxCenter = 0 # 记录最长回文子串的中心
        for i in range(len(s)):
            p[i] = min(p[2*id-i], mx-i) if i < mx else 1
            while i + p[i] < len(s) and i - p[i] > -1:
                if s[i+p[i]] == s[i-p[i]]:
                    p[i] += 1
                else:
                    break
            if i + p[i] > mx:
                mx = i + p[i]
                id = i
            if p[i] > res:
                maxCenter = i
                res = p[i]

        return ''.join(s[center-(res-1):center+res-1+1].split('#'))

    def init(self, s):

        res = '#'
        for i in range(len(s)):
            res += s[i]
            res += '#'
        return res
`

6. Z 字形变换

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LeetcodeISHIRING” 行数为 3 时，排列如下：

L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LeetcodeISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LeetcodeISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解题思路

将字符分为numRows保存，遍历字符串，从上到下和从下到上反复将字符加到对应的行里，当遍历到第一行时，index递增，当遍历到最后一行时，index递减。

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or numRows >= len(s):
            return s
        
        res = ['' for i in range(numRows)]
        index = 0
        step = 1
        
        for x in s:
            res[index] += x
            
            if index == 0:
                step = 1
            elif index == numRows-1:
                step = -1
                
            index += step
        
        return ''.join(res)

10. 正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

解题思路

以下超时，剑指中可以通过。

我们先来分析如何匹配一个字符，现在只考虑’.’，不考虑'*'：
如果字符串和模式串的当前字符相等，那么我们继续匹配它们的下一个字符；如果模式串中的字符是’.’，那么它可以匹配字符串中的任意字符，我们也可以继续匹配它们的下一个字符。

接下来，把字符'*'考虑进去，它可以匹配任意次的字符，当然出现0次也可以：
而当模式中的第二个字符是*时：
如果字符串第一个字符跟模式第一个字符匹配（包括模式串为’.’的情况），可以有3种匹配方式：

1. 模式后移2字符，相当于x*被忽略；
2. 字符串后移1字符，模式后移2字符，正好匹配x*中的'x'位；
3. 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
   如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配，相当于把模式串中的当前字符和'*'忽略掉。

当模式中的第二个字符不是*时，也就是上面说的只有字符’.’的情况。

1. 如果字符串第一个字符和模式中的第一个字符相匹配（包括模式串为’.’的情况），那么字符串和模式都后移一个字符，然后匹配剩余的。
2. 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        
        if not s and not p:
            return True
        if not p:
            return False
        
        if len(p) >= 2 and p[1] == "*":
            if s and (s[0] == p[0] or p[0] == "."):
                return self.isMatch(s[1:], p[2:]) or self.isMatch(s, p[2:]) or self.isMatch(s[1:], p)
            else:
                return self.isMatch(s, p[2:])
        else:
            if s and (s[0] == p[0] or p[0] == "."):
                return self.isMatch(s[1:],p[1:])
        
        return False

动态规划AC

定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况:
1.  P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2.  P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3.  P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

参考 https://www.cnblogs.com/grandyang/p/4461713.html

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        
        if not s and not p:
            return True
        if not p:
            return False
        
        dp = [[False]*(len(p)+1) for _ in range(len(s)+1)]
        dp[0][0] = True
        
        for i in range(len(s)+1):
            for j in range(1, len(p)+1):
                if j>1 and p[j-1] == '*':
                    dp[i][j] = (dp[i][j-2]) or (i>0 and dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
                else:
                    dp[i][j] = (i > 0) and dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
                    
        return dp[-1][-1]

14. 最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解题思路

首先把第一个字符串作为答案，然后遍历后面的字符串，当后面的字符串长度小于第一个字符串时，需要对第一个字符串进行裁剪，然后依次判断每一个字符是否相等，不相等时将第一个字符串裁剪。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ''
        
        res = strs[0]
        for i in range(1, len(strs)):
            
            if len(res) > len(strs[i]):
                res = res[:len(strs[i])]
            for j in range(len(res)):
                if res[j] != strs[i][j]:
                    res = res[:j]
                    break
            if res == '':
                return ''
            
        return res

30. 串联所有单词的子串

题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]

解题思路

用一个Map记录words中每个单词出现的次数。
遍历s，对于每一个位置进行判断。

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """

        if not s or not words:
            return []

        wordBag = {}
        for x in words:
            wordBag[x] = wordBag.get(x, 0) + 1

        wordLen, numWords = len(words[0]), len(words),
        totalLen = wordLen * numWords
        res = []

        for i in range(len(s) - totalLen + 1):
            seen = wordBag.copy() #深拷贝
            for j in range(i, i + totalLen, wordLen):
                curWord = s[j:j + wordLen]
                if curWord in wordBag:
                    seen[curWord] -= 1
                    if seen[curWord] < 0:
                        seen[curWord] = float('-inf') # 避免 [0,-1,1] sum(seen.values()) == 0 的情况
                        break
                else:
                    break
            if sum(seen.values()) == 0:
                res.append(i)

        return res

32. 最长有效括号

题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解题思路

思路一：遍历每个位置为起点，将’(‘看成1， ‘)’看成-1，如果和为0说明是有效括号，判断长度，如果和为负数，则说明一定无法构成有效括号，因为左边一定会多了一个’)’。

Python超时，JavaAC。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        res = 0
        for i in range(len(s)):
            num = 0
            for j in range(i, len(s)):
                num += 1 if s[j] == '(' else -1
                if num == 0 and res < j-i+1:
                    res = j-i+1
                elif num < 0:
                    break
        
        return res

class Solution {
    public int longestValidParentheses(String s) {
        
        char[] array = s.toCharArray();
        int num = 0;
        int res = 0;
        for (int i = 0; i<array.length; i++){
            num = 0;
            for (int j = i; j<array.length; j++){
                int temp = array[j] == '('?1:-1;
                num += temp;
                if (num == 0 && res < j-i+1){
                    res = j-i+1;
                }
                else if (num<0){
                    break;
                }
            }
        }
        return res;
    }
}

思路2：动态规划
新建一个dp数组，数组的每个位置表示包含该位置及之前的所有字符所形成的有效括号的长度。
从第二个下标开始遍历，
当S[i]=’)’及S[i-1]=’(‘，形成一个有效括号长度加2。
当S[i]=’)’及S[i-1]=’)’，判断S[i-1]形成的有效括号的前一位是否为’(‘，即S[i-dp[i-1]-1]是否为’(‘，如果是，则S[i-dp[i-1]-1]=’(‘和S[i]=’)’之间为有效括号，长度为dp[i-1]+2，然后再加上i-dp[i-1]-1的前一位i-dp[i-1]-2所形成的的有效括号数dp[i-dp[i-1]-2].

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """

        if len(s) <= 1:
            return 0
        dp = [0] * len(s)
        res = 0
        for i in range(1, len(s)):
            if s[i] == ')':
                if s[i - 1] == '(':
                    dp[i] = dp[i - 2] + 2 if i - 2 >= 0 else 2
                    res = max(res, dp[i])
                else:
                    if i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
                    	dp[i] = dp[i - 1] + 2
                        if i - dp[i - 1] - 2 >= 0:
                            dp[i] += dp[i - dp[i - 1] - 2]
                        
                        res = max(res, dp[i])
        return res

38. 报数

题目描述

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

• 1 被读作 “one 1” (“一个一”) , 即 11。
• 11 被读作 “two 1s” (“两个一”）, 即 21。
• 21 被读作 “one 2”, “one 1” （”一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

解题思路

class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return '1'
        
        pre = '1'
        for i in range(1, n):
            count = 1
            res = ''
            for j in range(1, len(pre)):
                if pre[j] == pre[j-1]:
                    count += 1
                else:
                    res += str(count) + pre[j-1]
                    count = 1
            res += str(count) + pre[-1]
            pre = res
        
        return res

44. 通配符匹配

题目描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false

解题思路

参考

这道题通配符外卡匹配问题还是小有难度的，有特殊字符 ‘’ 和 ‘?’，其中 ‘?’ 能代替任何字符，‘’ 能代替任何字符串，注意跟另一道 Regular Expression Matching 正则匹配的题目区分开来。两道题的星号的作用是不同的，注意对比区分一下。这道题最大的难点，就是对于星号的处理，可以匹配任意字符串，简直像开了挂一样，就是说在星号对应位置之前，不管你s中有任何字符串，我大星号都能匹配你，主角光环啊。但即便叼如斯的星号，也有其处理不了的问题，那就是一旦p中有s中不存在的字符，那么一定无法匹配，因为星号只能增加字符，不能消除字符，再有就是星号一旦确定了要匹配的字符串，对于星号位置后面的匹配情况也就鞭长莫及了。所以p串中星号的位置很重要，用 jStar 来表示，还有星号匹配到s串中的位置，使用 iStart 来表示，这里 iStar 和 jStar 均初始化为 -1，表示默认情况下是没有星号的。然后再用两个变量i和j分别指向当前s串和p串中遍历到的位置。

开始进行匹配，若i小于s串的长度，进行 while 循环。若当前两个字符相等，或着p中的字符是问号，则i和j分别加1。若 p[j] 是星号，那么我们要记录星号的位置，jStar 赋为j，此时j再自增1，iStar 赋为i。若当前 p[j] 不是星号，并且不能跟 p[i] 匹配上，那么此时就要靠星号了，若之前星号没出现过，那么就直接跪，比如 s = “aa” 和 p = “c“，此时 s[0] 和 p[0] 无法匹配，虽然 p[1] 是星号，但还是跪。如果星号之前出现过，可以强行续一波命，比如 s = “aa” 和 p = “c”，当发现 s[1] 和 p[1] 无法匹配时，但是好在之前 p[0] 出现了星号，我们把 s[1] 交给 p[0] 的星号去匹配。至于如何知道之前有没有星号，这时就能看出 iStar 的作用了，因为其初始化为 -1，而遇到星号时，其就会被更新为i，那么我们只要检测 iStar 的值，就能知道是否可以使用星号续命。虽然成功续了命，匹配完了s中的所有字符，但是之后我们还要检查p串，此时没匹配完的p串里只能剩星号，不能有其他的字符，将连续的星号过滤掉，如果j不等于p的长度，则返回false，参见代码如下：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        
        if p == "*":
            return True
        if p == '' and s == '':
            return True
        if p == '' or s == '':
            return False
        
        iStar, jStar = -1, -1
        i, j = 0, 0
        while i < len(s):
            if j<len(p) and (s[i] == p[j] or p[j] == '?'):
                i += 1
                j += 1
            elif j<len(p) and p[j] == "*":
                iStar = i
                jStar = j
                j += 1
            elif iStar >= 0:
                iStar += 1
                i = iStar
                j = jStar + 1
            else:
                return False
        
        while j < len(p) and p[j] == '*':
            j += 1
        return j == len(p)

这道题也能用动态规划 Dynamic Programming 来解，写法跟之前那道题 Regular Expression Matching 很像，但是还是不一样。外卡匹配和正则匹配最大的区别就是在星号的使用规则上，对于正则匹配来说，星号不能单独存在，前面必须要有一个字符，而星号存在的意义就是表明前面这个字符的个数可以是任意个，包括0个，那么就是说即使前面这个字符并没有在s中出现过也无所谓，只要后面的能匹配上就可以了。而外卡匹配就不是这样的，外卡匹配中的星号跟前面的字符没有半毛钱关系，如果前面的字符没有匹配上，那么直接返回 false 了，根本不用管星号。而星号存在的作用是可以表示任意的字符串，当然只是当匹配字符串缺少一些字符的时候起作用，当匹配字符串p包含目标字符串s中没有的字符时，将无法成功匹配。

对于这种玩字符串的题目，动态规划 Dynamic Programming 是一大神器，因为字符串跟其子串之间的关系十分密切，正好适合DP这种靠推导状态转移方程的特性。那么先来定义dp数组吧，我们使用一个二维 dp 数组，其中 dp[i][j] 表示 s中前i个字符组成的子串和p中前j个字符组成的子串是否能匹配。大小初始化为 (m+1) x (n+1)，加1的原因是要包含 dp[0][0] 的情况，因为若s和p都为空的话，也应该返回 true，所以也要初始化 dp[0][0] 为 true。还需要提前处理的一种情况是，当s为空，p为连续的星号时的情况。由于星号是可以代表空串的，所以只要s为空，那么连续的星号的位置都应该为 true，所以我们现将连续星号的位置都赋为 true。然后就是推导一般的状态转移方程了，如何更新 dp[i][j]，首先处理比较 tricky 的情况，若p中第j个字符是星号，由于星号可以匹配空串，所以如果p中的前 j-1 个字符跟s中前i个字符匹配成功了（ dp[i][j-1] 为true）的话，那么 dp[i][j] 也能为 true。或者若p中的前j个字符跟s中的前i-1个字符匹配成功了（ dp[i-1][j] 为true ）的话，那么 dp[i][j] 也能为 true（因为星号可以匹配任意字符串，再多加一个任意字符也没问题）。若p中的第j个字符不是星号，对于一般情况，我们假设已经知道了s中前 i-1 个字符和p中前 j-1 个字符的匹配情况（即 dp[i-1][j-1] ），那么现在只需要匹配s中的第i个字符跟p中的第j个字符，若二者相等（s[i-1] == p[j-1] ），或者p中的第j个字符是问号（ p[j-1] == '?' ），再与上 dp[i-1][j-1] 的值，就可以更新 dp[i][j] 了，参见代码如下：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        
        if p == "*":
            return True
        if p == '' and s == '':
            return True
        if p == '' or s == '':
            return False
        
        dp = [[False]*(len(p)+1) for _ in range(len(s)+1)]
        dp[0][0] = True
        for j in range(1, len(p)+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-1]
        
        for i in range(1, len(s)+1):
            for j in range(1, len(p)+1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
                else:
                    dp[i][j] = (s[i-1] == p[j-1] or p[j-1] == '?') and dp[i-1][j-1]
        
        return dp[-1][-1]

58. 最后一个单词的长度

题目描述

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例:

输入: "Hello World"
输出: 5

解题思路

库函数。

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        s = s.split()
        
        return len(s[-1]) if s else 0

双指针，一个指向最后一个单词的末尾，一个指向最后一个单词的开头。

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        left, right = 0, len(s)-1
        
        while right >= 0 and s[right] == ' ':
            right -= 1
        
        left = right
        
        while left >= 0 and s[left] != ' ':
            left -= 1
        
        return right - left

125. 验证回文串

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

• 说明：

  本题中，我们将空字符串定义为有效的回文串。

• 示例 1:

  输入: “A man, a plan, a canal: Panama”
  输出: true

• 示例 2:

  输入: “race a car”
  输出: false

解题思路

新建一个字符串，将所有数字字母保存；使用双指针，left从头向后遍历，right从后向前遍历，判断left和right指向的元素是否相等。

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == '':
            return True
        new = ''
        for x in s:
            if x.isalnum():
                new += x.lower()
        left, right = 0, len(new)-1
        while left <= right:
            if new[left] != new[right]:
                return False
            left += 1
            right -= 1
        return True
    
if __name__ == '__main__':
    result = Solution().isPalindrome("A man, a plan, a canal: Panama")
    print(result)

二刷

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) <= 1:
            return True
        
        s = s.lower()
        left, right = 0, len(s)-1
        
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        
        return True

131. 分割回文串

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解题思路

在每次回溯之前判断当前字符串是否为回文串。

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if not s:
            return []
        res = []
        self.dfs(s, [], res)
        return res
    
    def dfs(self, s, temp, res):
        if not s and temp:
            res.append(temp)
            return
        for i in range(1, len(s)+1):
            if self.isPalindrome(s[:i]):
                self.dfs(s[i:], temp+[s[:i]], res)
    
    def isPalindrome(self, s):
        # left, right = 0, len(s)-1
        # while left <= right:
        #     if s[left] != s[right]:
        #         return False
        #     left += 1
        #     right -= 1
        # return True
        return s == s[::-1]

139. 单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "Leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "Leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解题思路

dp[i]代表的时[0,i)满不满足单词拆分，需要遍历的范围为1~N+1，dp[0]初始化为True。
两层循环，外层循环遍历每个位置的状态，内层判断前面是否有一个位置j的状态为真 and 位置j到当前位置i是否在wordDict中。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        if not s:
            return True
        
        if len(wordDict) == 0:
            return False
        
        dp = [False] * (len(s)+1)
        dp[0] = True
        
        for i in range(1,len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
        return dp[-1]

151. 翻转字符串里的单词

题目描述

给定一个字符串，逐个翻转字符串中的每个单词。

示例:

输入: "the sky is blue",
输出: "blue is sky the".

说明:

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

解题思路

库函数

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return ' '.join(s.split()[::-1])

自己写的。先将头尾的空格去掉，新建一个字符串，将单词字符加入，去掉多余的空格。

然后先将整个字符串翻转，在将每个单词翻转。

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""
        left = 0
        while left < len(s) and s[left] == ' ':
            left += 1
        right = len(s)-1
        while right >= 0 and s[right] == ' ':
            right -= 1
        s = s[left:right+1]

        newstring = ''
        i = 0
        while i < len(s):
            if s[i] != ' ':
                newstring += s[i]
                i += 1
            else:
                newstring += ' '
                while i < len(s) and s[i] == ' ':
                    i += 1

        newstring = list(newstring)
        self.reverse(newstring, 0, len(newstring))
        start, end = 0, 0
        while end < len(newstring):
            while end < len(newstring) and newstring[end] != ' ':
                end += 1
            self.reverse(newstring, start, end)
            start = end + 1
            end = start

        return ''.join(newstring)

    def reverse(self, s, start, end):
        left, right = start, end-1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

165. 比较版本号

题目描述

比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。

你可以假设版本字符串非空，并且只包含数字和 . 字符。

. 字符不代表小数点，而是用于分隔数字序列。

例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。

你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。

示例 1:

输入: version1 = "0.1", version2 = "1.1"
输出: -1

示例 2:

输入: version1 = "1.0.1", version2 = "1"
输出: 1

示例 3:

输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1

示例 4：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，“01” 和 “001” 表示相同的数字 “1”。

示例 5：

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有第三级修订号，这意味着它的第三级修订号默认为 “0”。

提示：

• 版本字符串由以点 （.） 分隔的数字字符串组成。这个数字字符串可能有前导零。
• 版本字符串不以点开始或结束，并且其中不会有两个连续的点。

解题思路

先将两个版本号以’.’分隔为两个列表，然后按位比较，短的补零。

class Solution(object):
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        
        if not version1 or not version2:
            return 0
        
        version1 = version1.split('.')
        version2 = version2.split('.')
        
        i = 0
        while i < len(version1) or i < len(version2):
            
            v1 = version1[i] if i < len(version1) else 0
            v2 = version2[i] if i < len(version2) else 0
            if int(v1) > int(v2):
                return 1
            if int(v1) < int(v2):
                return -1
            i += 1
            
        return 0

227. 基本计算器 II

题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

解题思路

用num保存上一个数字，用pre_op保存上一个操作符。当遇到新的操作符的时候，需要根据pre_op进行操作。乘除的优先级高于加减。所以有以下规则：

之前的运算符是+，那么需要把之前的数字num进栈，然后等待下一个操作数的到来。

之前的运算符是-，那么需要把之前的数字求反-num进栈，然后等待下一个操作数的到来。

之前的运算符是×，那么需要立刻出栈和之前的数字相乘，重新进栈，然后等待下一个操作数的到来。

之前的运算符是/，那么需要立刻出栈和之前的数字相除，重新进栈，然后等待下一个操作数的到来。

注意比较的都是之前的操作符和操作数，现在遇到的操作符是没有什么用的。

另外，坑爹的Python地板除。

参考

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        if len(s) == 0:
            return 0
        
        stack = []
        num = 0
        pre_op = '+'
        
        for i in range(len(s)):
            if s[i] in '0123456789':
                num = num*10+int(s[i])
            if i == len(s)-1 or s[i] in '+-*/':
                if pre_op == '+':
                    stack.append(num)
                elif pre_op == '-':
                    stack.append(-num)
                elif pre_op == '*':
                    stack.append(stack.pop()*num)
                elif pre_op == '/':
                    top = stack.pop()
                    if top*num < 0 and top % num != 0:
                        stack.append(top // num + 1)
                    else:
                        stack.append(top // num)
                pre_op = s[i]
                num = 0
        
        return sum(stack)

344. 反转字符串

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

解题思路

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        
        s[:] = s[::-1]

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        
        left, right = 0, len(s)-1
        
        while left < right:
            s[left], s[right] = s[right], s[left]
            left, right = left + 1, right - 1

        return

345. 反转字符串中的元音字母

题目描述

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "Leetcode"
输出: "leotcede"

说明:
元音字母不包含字母”y”。

解题思路

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        s = list(s)
        left, right = 0, len(s)-1
        
        while left < right:
            while left < right and s[left] not in 'aAeEiIoOuU':
                left += 1
            while right > left and s[right] not in 'aAeEiIoOuU':
                right -= 1
            s[left], s[right] = s[right], s[left]
            left, right = left+1, right-1
            
        return ''.join(s)

383. 赎金信

题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

解题思路

遍历ransomNote，如果不在magazine，返回False，如果在，删除magazine中对应的字符。

需要转成list才可以用remove。

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        """
        :type ransomNote: str
        :type magazine: str
        :rtype: bool
        """
        
        if len(ransomNote ) == 0:
            return True
        if len(magazine) == 0:
            return False
        
        magazine = list(magazine)
        
        for x in ransomNote:
            if x not in magazine:
                return False
            else:
                magazine.remove(x)
        
        return True

385. 迷你语法分析器

题目描述

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

列表中的每个元素只可能是整数或整数嵌套列表

提示：你可以假定这些字符串都是格式良好的：

字符串非空
字符串不包含空格
字符串只包含数字0-9, [, - ,, ]

示例 1：

给定 s = "324",

你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

给定 s = "[123,[456,[789]]]",

返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
    i.  一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
         a. 一个 integer 包含值 789

解题思路

不太理解。
参考

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class Solution(object):
    def deserialize(self, s):
        """
        :type s: str
        :rtype: NestedInteger
        """
        if len(s) == 0:
            return NestedInteger()
        
        if s[0] != '[':
            return NestedInteger(int(s))
        
        res = NestedInteger()
        numP, start = 0, 1
        for i in range(1, len(s)):
            if (numP == 0 and s[i] == ',') or i == len(s)-1:
                if start < i:
                    res.add(self.deserialize(s[start:i]))
                start = i + 1
            elif s[i] == '[':
                numP += 1
            elif s[i] == ']':
                numP -= 1
        
        return res

387. 字符串中的第一个唯一字符

题目描述

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "Leetcode"
返回 0.

s = "loveLeetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

解题思路

两次遍历

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        if len(s) == 0:
            return -1
        
        Dict = {}
        for x in s:
            if x not in Dict:
                Dict[x] = 1
            else:
                Dict[x] += 1
        
        for i in range(len(s)):
            if Dict[s[i]] == 1:
                return i
        
        return -1

415. 字符串相加

题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

1. num1 和num2 的长度都小于 5100.
2. num1 和num2 都只包含数字 0-9.
3. num1 和num2 都不包含任何前导零。
4. 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

解题思路

class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        
        
        midsum = []
        
        num1, num2 = num1[::-1], num2[::-1]
        
        index = 0
        while index < len(num1) and index < len(num2):
            midsum.append(ord(num1[index])-48 + ord(num2[index]) - 48)
            index += 1
        
        if index == len(num1):
            for i in range(index, len(num2)):
                midsum.append(ord(num2[i]) - 48)
        else:
            for i in range(index, len(num1)):
                midsum.append(ord(num1[i]) - 48)
        
        res = ''
        plus = 0
        for x in midsum:
            num = plus + x
            res = str(num % 10) + res
            plus = num // 10
            
        if plus:
            res = str(plus) + res
        
        return res

434. 字符串中的单词数

题目描述

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: "Hello, my name is John"
输出: 5

解题思路

class Solution(object):
    def countSegments(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        s = s.split()
        
        return len(s)