面试必刷TOP101：字符串（83-86，Python实现）

83.字符串变形（小试牛刀）

83.1 两次反序

step 1：遍历字符串，遇到小写字母，转换成大写，遇到大写字母，转换成小写，遇到空格正常不变。
step 2：第一次反转整个字符串，这样基本的单词逆序就有了，但是每个单词的字符也是逆的。
step 3：再次遍历字符串，以每个空间为界，将每个单词反转回正常。

class Solution:
    def trans(self , s: str, n: int) -> str:
        if n == 0:
            return 0
        res = ''
        # 大小写转换
        for  i in range(n):
            if s[i] >= 'A' and s[i] <= 'Z':
                res = res + chr(ord(s[i])-ord('A')+ord('a'))
            elif s[i] >= 'a' and s[i] <= 'z':
                res = res + chr(ord(s[i])-ord('a')+ord('A'))
            else:
                res = res + s[i]
        # 单词反序
        res = list(res.split(' '))[::-1]
        return ' '.join(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：$O(n)$，虽有多个循环，但是每个循环都只有一层 $O(n)$。
空间复杂度：$O(n)$，$res$ 是存储变换的临时字符串，也可以直接用 $s$ 直接变换，这样就为 $O(1)$。

83.2 辅助栈

step 1：遍历字符串，遇到小写字母，转换成大写，遇到大写字母，转换成小写，遇到空格正常不变。
step 2：按照空格把字符串分割成一个个单词.
step 3：遍历分割好的单词，将单词依次存入栈中。
step 4：再从栈中弹出单词，拼接成字符串。

此种方法略显麻烦，不在此处给出代码，仅供参考。

84.最长公共前缀（小试牛刀）

84.1 遍历查找

既然是公共前缀，那我们可以用一个字符串与其他字符串进行比较，从第一个字符开始，逐位比较，找到最长公共子串。

step 1：处理数组为空的特殊情况。
step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第 $i$ 位开始不同，前面的都是公共前缀。
step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        n = len(strs)
        if n == 0:
            return ''
        for i in range(len(strs[0])):
            temp = strs[0][i]
            for j in range(1,n):
                if i == len(strs[j]) or strs[j][i] != temp:
                    return strs[0][0:i]
        return strs[0]
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：$O(mn)$，其中 $m$ 为数组中最短的字符串的长度，$n$ 为字符串数组的长度，两层遍历循环。
空间复杂度：$O(1)$，常数级变量，没有使用额外的辅助空间。

85.验证IP地址（小试牛刀）

85.1 分割比较

我们可以先对IP字符串进行分割，然后依次判断每个分割是否符合要求。

step 1：写一个 $split$ 函数（或者内置函数）。
step 2：遍历 $IP$ 字符串，遇到 . 或者 : 将其分开储存在一个数组中。
step 3：遍历数组，对于 $IPv4$，需要依次验证分组为 $4$，分割不能缺省，没有前缀 $0$ 或者其他字符，数字在 $0-255$ 范围内。
step 4：对于 $IPv6$，需要依次验证分组为 $8$，分割不能缺省，每组不能超过 $4$ 位，不能出现除数字小大写 $a-f$ 以外的字符。

class Solution:
    def isIPv4(self, IP:str):
        s = IP.split('.')
        print(s)
        if len(s) != 4:
            return False
        for i in range(len(s)):
            if len(s[i]) == 0 or len(s[i]) > 3 or (s[i][0] == '0' and len(s[i]) != 1):
                return False
            for j in range(len(s[i])):
                if s[i][j] < '0' or s[i][j] > '9':
                    return False
            num = int(s[i])
            if num < 0 or num > 255:
                return False
        return True

    def isIPv6(self, IP:str):
        s = IP.split(':')
        if len(s) != 8:
            return False
        for i in range(len(s)):
            if len(s[i]) == 0 or len(s[i]) > 4:
                return False
            for j in range(len(s[i])):
                if not (s[i][j].isdigit() or s[i][j] >= 'a' and s[i][j] <= 'f' or s[i][j] >= 'A' and s[i][j] <= 'F'):
                        return False
        return True
            
    def solve(self , IP: str) -> str:
        if len(IP) == 0:
            return 'Neither'
        if self.isIPv4(IP):
            return 'IPv4'
        if self.isIPv6(IP):
            return 'IPv6'
        return 'Neither'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

时间复杂度：$O(n)$，n 为字符串 $IP$ 的长度，判断部分只遍历 4 组或者 8 组，但是分割字符串需要遍历全部。
空间复杂度：$O(1)$，储存分割字符串的临时空间为常数 4 或者 8。

85.2 正则表达式

import re
class Solution:    
    def solve(self , IP: str) -> str:
        # 正则表达式限制 0-255 且没有前缀0 四组齐全
        ipv4 = "(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])"
        # 正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个
        ipv6 = "([0-9a-fA-F]{1,4}\:){7}([0-9a-fA-F]{1,4})$"
        ipv4 = re.compile(ipv4)
        ipv6 = re.compile(ipv6)
        # 调用正则匹配函数
        if ipv4.match(IP):
            return "IPv4"
        elif ipv6.match(IP):
            return "IPv6"
        else:
            return "Neither"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：$O(n)$，$regex\_match$ 函数默认 $O(n)$。
空间复杂度：$O(1)$，没有使用额外空间。

86.大数加法（小试牛刀）

86.1 模拟法

大整数相加，就可以按照整数相加的方式，从个位开始，逐渐往上累加，换到字符串中就是从两个字符串的末尾开始相加。

step 1：若是其中一个字符串为空，直接返回另一个，不用加了。
step 2：交换两个字符串的位置，我们是 $s$ 为较长的字符串，$t$ 为较短的字符串，结果也记录在较长的字符串中。
step 3：从后往前遍历字符串 $s$，每次取出字符转数字，加上进位制，将下标转换为字符串 $t$ 中从后往前相应的下标，如果下标为非负数则还需要加上字符串 $t$ 中相应字符转化的数字。
step 4：整型除法取进位，取模算法去掉十位，将计算后的结果放入较长数组对应位置。
step 5：如果遍历结束，进位值还有，则需要直接在字符串 $s$ 前增加一个字符 $‘1’$。

class Solution:
    def solve(self , s: str, t: str) -> str:
        if len(s) == 0:
            return t
        if len(t) == 0:
            return s
        # 让 s 为较长的
        if len(s) < len(t):
            s, t = t, s
        # 进位标志
        carry = 0
        i = len(s) - 1
        j = len(t) - 1
        # 从后往前遍历较长的字符串
        while i >= 0:
            temp = int(s[i]) + carry
            if j >= 0:
                temp = temp + int(t[j])
            # 取进位
            carry = int(temp / 10)
            # 去十位
            temp = temp % 10
            s = s[:i] + str(temp) + s[i+1:]
            i = i - 1
            j = j - 1
        if carry == 1:
            s = '1' + s
        return s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：$O(n)$，其中 $n$ 为较长字符的长度，遍历字符串。
空间复杂度：$O(1)$，常数级空间，没有使用额外辅助空间。