字符串

LeetCode中的字符串标题是指需求对字符串进行操作或处理的标题，包括字符串的匹配、替换、排序、翻转、去重、切割等等操作。字符串标题常见的难点在于怎么处理字符串的鸿沟条件，如空字符串、只包括空格的字符串、字符串长度为1等特殊情况，以及字符串中的特殊字符（如空格、数字、字母等）的处理。

常见的字符串标题有：

1. 完成 strStr() 函数：在一个字符串中查找另一个字符串的方位

2. 回转字符串：将一个字符串回转

3. 回转字符串中的单词：将一个字符串中的单词次序回转

4. 有效的括号：判别一个字符串中的括号是否匹配

5. 最长公共前缀：查找多个字符串中最长的公共前缀

6. 翻转字符串里的单词 III：将一个字符串中每个单词回转

7. 字符串转换整数 (atoi)：将一个字符串转换为整数

8. 无重复字符的最长子串：查找一个字符串中最长的不包括重复字符的子串

这些标题关于把握字符串的基本操作、鸿沟处理以及算法思维都有很好的操练效果。

---

151. 回转字符串中的单词 – 力扣（Leetcode）

给你一个字符串s，请你回转字符串中单词的次序。

单词是由非空格字符组成的字符串。s中运用至少一个空格将字符串中的单词分离隔。

回来单词次序颠倒且单词之间用单个空格衔接的成果字符串。

注意： 输入字符串s中可能会存在前导空格、跟随空格或许单词间的多个空格。回来的成果字符串中，单词间应当仅用单个空格分隔，且不包括任何额定的空格。

示例 1：

输入： s = "the sky is blue"
输出： "blue is sky the"

示例 2：

输入： s = " hello world "
输出： "world hello"
解说： 回转后的字符串中不能存在前导空格和跟随空格。

示例 3：

输入： s = "a good  example"
输出： "example good a"
解说： 假如两个单词间有剩余的空格，回转后的字符串需求将单词间的空格削减到仅有一个。

提示：

• 1 <= s.length <= 104
• s包括英文大小写字母、数字和空格' '
• s中至少存在一个单词

进阶： 假如字符串在你运用的编程语言中是一种可变数据类型，请测验运用O(1)额定空间复杂度的原地解法。

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.split(' ')
        ans = ''
        for i in range(len(s)-1,-1,-1):
            if s[i]:
                ans += s[i] + ' '
        return ans.strip()

函数的完成办法是先运用 split() 办法将字符串依照空格切割成一个个单词，然后从后往前遍历每个单词，并将非空单词参加答案字符串 ans 中，并在单词之间加上一个空格。最后回来答案字符串时，运用 strip() 办法将首尾剩余的空格去掉。

这个函数的时刻复杂度为 $O(n)$，其间 $n$ 是字符串的长度。空间复杂度取决于单词的个数，由于需求将每个单词存储在一个新的字符串中，所以空间复杂度为 $O(k)$，其间 $k$ 是单词的个数。

在 Python 中，字符串是不可变（immutable）的数据类型，这意味着一旦创建了一个字符串目标，就无法修正它的值。假如需求修正一个字符串，需求创建一个新的字符串目标，而不是修正原始的字符串目标。这个特性是由于 Python 中的字符串被视为一系列 Unicode 字符的序列，而这些字符在创建后是不能更改的。假如需求进行字符串的修正操作，可以运用一些字符串操作函数来完成，例如字符串切片、衔接、替换等。

所以， 进阶问题我选择不进阶。

14. 最长公共前缀 – 力扣（Leetcode）

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

假如不存在公共前缀，回来空字符串""。

示例 1：

输入： strs = ["flower","flow","flight"]
输出： "fl"

示例 2：

输入： strs = ["dog","racecar","car"]
输出： ""
解说： 输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]仅由小写英文字母组成

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ''
        for i in zip(*strs): 
            if len(set(i)) == 1:
                ans += i[0]
            else:
                break
        return ans

这个函数承受一个字符串数组 strs 作为输入，回来一个字符串，表明数组中一切字符串的最长公共前缀。

函数运用了 zip(*strs) 技巧，将字符串数组转换为元组数组，并按列进行迭代。关于每一列中的字符，假如它们都相同，则将其参加到最长公共前缀中，直到呈现不同的字符或许一切字符串遍历结束。终究回来最长公共前缀即可。

需求注意的是，假如输入的字符串数组为空或许其间恣意一个字符串为空，则最长公共前缀应该是空字符串。

---

28. 找出字符串中第一个匹配项的下标 – 力扣（Leetcode）

给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。假如needle不是haystack的一部分，则回来-1 ****。

示例 1：

输入： haystack = "sadbutsad", needle = "sad"
输出： 0
解说： "sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以回来 0 。

示例 2：

输入： haystack = "leetcode", needle = "leeto"
输出： -1
解说： "leeto" 没有在 "leetcode" 中呈现，所以回来 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack和needle仅由小写英文字符组成

class Solution:
  def strStr(self, haystack: str, needle: str) -> int:
    return haystack.index(needle) if needle in haystack else -1

代码完成了如下逻辑：

1. 判别needle是否存在于haystack中，假如存在，回来needle在haystack中第一次呈现的方位，即运用index()函数回来的成果；

2. 假如needle不存在于haystack中，回来-1。

需求注意的是，当needle不存在于haystack中时，调用index()函数会抛出ValueError反常，因而在代码中运用了if语句进行了反常处理，将其转换为回来-1的成果。

这个算法的时刻复杂度是 O(nm)，其间 n 是 haystack 字符串的长度，m 是 needle 字符串的长度。这是由于在最坏情况下，需求比较 haystack 字符串中的每个方位和 needle 字符串中的每个方位，才能确认 needle 是否存在于 haystack 中。

空间复杂度是 O(1)，由于算法中只运用了常数等级的额定空间。

6. N 字形改换 – 力扣（Leetcode）

将一个给定字符串s依据给定的行数numRows，以从上往下、从左到右进行Z 字形摆放。

比方输入字符串为"PAYPALISHIRING"行数为3时，摆放如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需求从左往右逐行读取，产生出一个新的字符串，比方："PAHNAPLSIIGYIR"。

请你完成这个将字符串进行指定行数改换的函数：

string convert(string s, int numRows);

示例 1：

输入： s = "PAYPALISHIRING", numRows = 3
输出： "PAHNAPLSIIGYIR"

示例 2：

输入： s = "PAYPALISHIRING", numRows = 4
输出： "PINALSIGYAHRPI"
解说：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入： s = "A", numRows = 1
输出： "A"

提示：

• 1 <= s.length <= 1000
• s由英文字母（小写和大写）、','和'.'组成
• 1 <= numRows <= 1000

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows<2: return s
        res = ['' for _ in range(numRows)]
        i = 0
        flag = -1
        for c in s:
            res[i] += c
            if i==0 or i == numRows-1:
                flag = -flag
            i += flag
        return ''.join(res)

这段代码完成了将一个字符串依照锯齿形摆放并输出的功能。锯齿形摆放的行数由参数numRows给定，每个字符被填充在对应行上，终究从上到下、从左到右依次读出每个字符得到输出成果。

该办法的主要思路是模仿整个锯齿形状的过程，用一个数组res来保存每行的字符，初始时一切行都为空字符串。然后遍历字符串s中的每个字符，将其参加到res中对应的行。i表明当时正在处理的行号，flag表明i的变化方向，当i到达第一行或最后一行时，需求将flag取反，以改动i的增减方向。最后将res数组中的每行拼接起来即可。

这个办法的时刻复杂度为O(n)，其间n为字符串s的长度，由于只需求遍历一次s就可以得到终究成果。空间复杂度为O(numRows)，需求一个数组来保存每行的字符。假如numRows非常大，空间开支会很大，因而需求依据实际情况进行优化。