初级算法-字符串
知识
数组是一种线性数据结构，其常见复杂度如下：
查找O(n)，删除O(n)，插入O(n)，随机读取O(1)
若初始化一个定长数组，可以降低复杂度，但将会失去可变数组带来的简便添加元素和删除元素的方法。
大部分情况下，字符串可以视作数组（或是列表）来考虑。
技巧
转换列表
使用list()函数，将字符串转为列表，再用for循环将结果重新添加回字符串，这是没有更好解决办法时可以使用的技巧。
练习
344. 反转字符串
问题：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]提示：
1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符解答：
class Solution:
# 双指针法
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
m = 0
n = 1
while m<=len(s)/2 and n<=len(s)/2:
s[m], s[-n] = s[-n], s[m]
m += 1
n += 1
# 列表反转法
def reverseString(self, s: List[str]) -> None:
s[:] = s[::-1]
# 使用 reverse() 函数
def reverseString(self, s: List[str]) -> None:
s = s.reverse() 7. 整数反转
问题：
https://leetcode-cn.com/problems/reverse-integer/
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 $[−2^{31}, 2^{31} − 1] $，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
解答：
首次解答：
class Solution:
def reverse(self, x: int) -> int:
k = ''
# 取出正负号
if x < 0:
x = -x
for i in list(str(x))[::-1]:
k += i
# 判断反转后大小是否在范围内
if -(2**31) > 0-int(k) or 0-int(k) > 2**31 - 1 :
return 0
else:
return 0-int(k)
if x >= 0:
for i in list(str(x))[::-1]:
k += i
if -(2**31) > int(k) or int(k) > 2**31 - 1 :
return 0
else:
return int(k)不过，这样来写，在代码上还是比较复杂的，更简单的写法可以考虑使用%和//运算。
再次解答：
387. 字符串中的第一个唯一字符
问题：
https://leetcode-cn.com/problems/first-unique-character-in-a-string/
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
示例 1：
输入: s = "leetcode"
输出: 0示例 2:
输入: s = "loveleetcode"
输出: 2示例 3:
输入: s = "aabb"
输出: -1提示:
1 <= s.length <= 105
s 只包含小写字母解答：
class Solution:
# 使用count()函数
def firstUniqChar(self, s: str) -> int:
for idx in range(len(s)):
if s.count(s[idx]) == 1:
return idx
return -1
# 使用字典等可变结构
def firstUniqChar(self, s: str) -> int:
k = {}
p = {}
for idx in range(len(s)):
if s[idx] in k and s[idx] in p:
p.pop(s[idx])
continue
elif s[idx] not in k:
k[s[idx]] = idx
p[s[idx]] = idx
if p != {}:
return list(p.values())[0]
else:
return -1但其实，双字典（哈希表）对空间的占用还是大了，观察可知，除了唯一需要的idx之外，其它的字符位置都是不需要的。那么，可以通过修改value来减少字典的使用。
class Solution:
def firstUniqChar(self, s: str) -> int:
k = {}; first = len(s)
for idx in range(len(s)):
if s[idx] in k:
k[s[idx]] = -1
continue
elif s[idx] not in k:
k[s[idx]] = idx
for v in k.values():
if v != -1 and v < first:
first = v
if first == len(s):
return -1
else: return first因为第二个for所需的最大运行时长固定，所以用时会更短。
242. 有效的字母异位词
问题：
https://leetcode-cn.com/problems/valid-anagram/
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true示例 2:
输入: s = "rat", t = "car"
输出: false提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母解答：
class Solution:
# 使用count()
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
k = []
for i in s:
if i not in k:
if s.count(i) != t.count(i):
return False
k.append(i)
return True
# 使用字典
def isAnagram(self, s: str, t: str) -> bool:125. 验证回文串
问题：
https://leetcode-cn.com/problems/valid-palindrome/
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串提示：
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成解答：
class Solution:
# 硬写，双指针
def isPalindrome(self, s: str) -> bool:
m = 0
n = 1
while m < len(s)-n:
if ord(s[m])<48 or 57<ord(s[m])<65 or 90<ord(s[m])<97 or ord(s[m])>122:
m = m + 1
elif ord(s[-n])<48 or 57<ord(s[-n])<65 or 90<ord(s[-n])<97 or ord(s[-n])>122:
n = n + 1
else:
if ord(s[m]) == ord(s[-n]) or ord(s[m]) == ord(s[-n]) + 32 or ord(s[m]) + 32 == ord(s[-n]):
if ord(s[m]) != ord(s[-n]):
if ord(s[m])<58 or ord(s[-n])<58:
return False
m += 1; n += 1
else:
return False
return True8. 字符串转换整数 (atoi)
问题：
https://leetcode-cn.com/problems/string-to-integer-atoi
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数myAtoi(string s)的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 $[−2^{31}, 2^{31} − 1]$ ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 $−2^{31}$ 的整数应该被固定为 $−2^{31}$ ，大于 $2^{31} − 1$ 的整数应该被固定为 $2^{31} − 1$。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。解答：
28. 实现 strStr()
问题：
https://leetcode-cn.com/problems/implement-strstr
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1示例 3：
输入：haystack = "", needle = ""
输出：0提示：
1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成解答：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if haystack == needle == '' or needle == '':
return 0
elif haystack == '':
return -1
else:
# 这个地方有点作弊了，或许不应该用 in 这个效果。
if needle in haystack:
for idx in range(len(haystack)):
k = 0
if list(haystack)[idx] == list(needle)[0]:
for iidx in range(len(needle)):
if list(needle)[iidx] == list(haystack)[idx+iidx]:
k += 1
if k == len(needle):
return idx
else:
return -138. 外观数列
问题：
https://leetcode-cn.com/problems/count-and-say/
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。例如，数字字符串 “3322251” 的描述如下图：
示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"提示：
1 <= n <= 30解答：
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1: return '1'
else:
# 设置递归
s = self.countAndSay(n-1)
cnt, digit = 0, s[0]
res = ''
for ch in s:
if ch == digit:
cnt += 1
else:
res += f'{cnt}{digit}'
digit = ch
cnt = 1
return f'{res}{cnt}{digit}'14. 最长公共前缀
问题：
https://leetcode-cn.com/problems/longest-common-prefix/
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 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:
p = []
if len(strs) > 1:
for i in range(len(strs[0])):
m = strs[0][i]
# 虽然try except有效，但这种写法还是太怪了一点。
try:
for k in strs:
if k[i] == m:
continue
else:
# 重复部分
x = ''
for t in p:
x += t
return x
p.append(m)
except Exception:
# 重复部分
x = ''
for t in p:
x += t
return x
# 重复部分
x = ''
for t in p:
x += t
return x
else:
return strs[0] 上述代码重复部分太多，同时使用了try except结构，非常需要优化的。
这种情况的出现，是因为对整个题目和解法进行了很直接的判断，出现问题就解决问题，于是打了多次补丁来针对性地解决问题。这并不是一个正确的思路。
在书写代码遇到对模式的直接模拟出现错误时，单纯地使用增量代码的方式补足缺陷是不好的。更好的办法是修改当前代码的模式，通过改变此时代码在非判断和非循环下的适应性才是更合适的。
确切来说，当模拟模式时，需要考虑的不是直观模式，而是代码结构对非直观模式的反映和处理。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res, col = '', 0
while True:
# 不变的矩阵查找
ch = strs[0][col]
# 循环
for row in strs[1:]:
# 通过新的判断语句避免out of range
if col == len(row) and row[col] != ch:
return res
res += ch
col += 1同样，也可以写成下面这种形式：
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0: return ''
res = ''
for chs in zip(*strs):
if len(set(chs)) == 1:
res += chs[0]
else: return res
return res