11.字符串

# `① 栈（Stack）`

# 01.有效的括号

20.有效的括号 (opens new window)

# 事例1
输入：s = "()[]{}"
输出：true
# 事例2
输入：s = "(]"
输出：false

1
2
3
4
5
6

1、Python

如果是左括号直接入栈，如果右边括号判断栈顶是否时对应左括号
如果左右括号匹配栈顶出栈，最终判断是否栈为空

class Solution:
    def isValid(self, s):
        d = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = []
        for ch in s:
            if ch in d:        # 如果字符串是 右边括号判断栈顶是否时对应左括号
                if not stack or stack[-1] != d[ch]:
                    return False
                stack.pop()   # 如果 左右括号匹配 栈顶出栈
            else:
                stack.append(ch)  # 如果是左侧括号，直接入栈
        return not stack

if __name__== "__main__":
    print(Solution().isValid("([]{})"))  # True
    print(Solution().isValid("([(])"))  # False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 02.最长有效括号

32.最长有效括号 (opens new window)

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

1
2
3
4
5
6
7

1、Python

使用一个栈来记录索引，初始时我们将 -1 压入栈中，这可以帮助我们处理最开始的有效子串
遍历字符串s中的每一个字符：
- 如果字符是 '('，我们将它的索引压入栈中
- 如果字符是 ')'，我们弹出栈顶的元素如果此时栈为空，说明没有匹配的 '('，我们将当前索引压入栈中
- 如果栈不为空，我们计算当前有效括号的长度，即当前索引减去栈顶元素的索引，并更新最大长度
遍历结束后，最大长度即为最长有效括号的长度

class Solution:
    def longestValidParentheses(self, s):
        stack = [-1]  # 栈初始存入 -1 以便计算长度
        max_len = 0

        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()  # stack为空 证明 当栈顶只有一个元素时出现了右括号，必然不符合要求[-1,)]
                if not stack:
                    stack.append(i) # 如果栈为空，压入当前索引
                else:
                    max_len = max(max_len, i - stack[-1])  # 计算最大长度

        return max_len

print(Solution().longestValidParentheses("(()"))     # 输出：2
print(Solution().longestValidParentheses(")()())"))  # 输出：4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 03.反转字符串中的单词 III

557.反转字符串中的单词 III (opens new window)
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

1
2

1、Python

利用栈的先进后出的结构很容易做到字符反转
但一串英文单词中，单词的个数总是比空格的字数多一个，在处理的时候很不方便
- 我们不妨在原字符串末尾补充一个空格，让每一小节都变成“单词+空格”
- 遇见空格就是我们判断出栈的前提条件
- 于是我们只要利用切片返回第一个字符后面的string就可以了

def reverseWords(s):
    stack = []   # 使用列表模拟栈
    new_s = ""   # new_s 新字符串
    s = s + " "  # 原字符串末尾补充一个空格，让每一小节都变成“单词+空格”
    for i in s:
        stack.append(i)  # 只要没有遇到空格就依次进栈
        if i == " ":     # 如果遇到空格依次出栈，这样就实现了反转
            while(stack):
                new_s += stack.pop()
    return new_s[1:]

print( reverseWords( "I love you" ) )  # I evol uoy

1
2
3
4
5
6
7
8
9
10
11
12

2、Python基本反转

'''第一种：使用字符串切片'''
s = 'Hello World'
print(s[::-1])  # dlroW olleH

'''第二种：使用列表的reverse方法'''
l = list(s)
l.reverse()
print( "".join(l) )   # dlroW olleH

'''第三种：使用reduce'''
from functools import reduce
result = reduce(lambda x,y:y+x,s)
print( result )      # dlroW olleH

1
2
3
4
5
6
7
8
9
10
11
12
13

# 04.去除重复字母

316.去除重复字母 (opens new window)
- 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
- 需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）
1081.不同字符的最小子序列 (opens new window)
- 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次

输入：s = "bcabc"
输出："abc"

输入：s = "cbacdcbc"
输出："acdb"

1
2
3
4
5

1、Python

使用 stack 作为单调栈，存储最终结果
如果 1.当前字符 < 栈顶字符 2.栈顶字符后面还出现 (dic_cnt[stack[-1]] > 0)
证明 使用当前元素替换栈顶元素 会使字典序列更小，替换即可

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        dic_cnt = {}  # 每个字符出现次数: {'c': 4, 'b': 2, 'a': 1, 'd': 1}
        for c in s:
            dic_cnt[c] = dic_cnt.get(c, 0) + 1

        set_ = set()  # set_ 记录栈中的字符，确保字符不重复
        stack = []    # stack 作为单调栈，存储最终结果，保证字典序最小

        for c in s:
            dic_cnt[c] -= 1  # 当前字符的计数减1，表示它已被访问一次
            if c in set_:    # 如果字符已在栈中，跳过，避免重复
                continue

            # 1. 当前字符 < 栈顶字符  2. 栈顶字符后面还出现 (dic_cnt[stack[-1]] > 0)
            while stack and c < stack[-1] and dic_cnt[stack[-1]] > 0:
                set_.remove(stack.pop())            # 弹出栈顶换当前字符(会更小)
            stack.append(c)            # 将当前字符加入栈，并标记为已加入
            set_.add(c)
        return ''.join(stack)

print(Solution().smallestSubsequence("cbacdcbc"))  # 输出: "acdb"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 05.字符串解码

394.字符串解码 (opens new window)
给定一个经过编码的字符串，返回它解码后的字符串
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次
你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

1
2
3
4
5

1、Python

使用栈处理嵌套的重复字符串
当遇到 [ 时，保存当前字符串和重复次数
遇到 ] 时，弹出栈顶并拼接重复子串
普通字符直接追加到当前字符串最终构造出解码后的字符串

def decodeString(s):
    stack = []            # 存储左右括号 和临时结果 [('b', 3), ('a', 2)]
    cur_str = ''          # 存储当前的解析字符串
    cur_num = 0           # 解析字符数量

    for c in s:
        print(c, stack, cur_str)
        if c.isdigit():
            cur_num = cur_num * 10 + int(c)   # 处理多位数字，计算重复次数
        elif c == '[':      # 遇到左括号，将当前字符串和数字存入栈
            stack.append((cur_str, cur_num))  # 左括号 [('b', 3), ('a', 2)]
            cur_str = ''    # 重置当前字符串
            cur_num = 0     # 重置数量
        elif c == ']':      # 遇到右括号，计算栈顶子串
            last_str, num = stack.pop()          # last_str, num =  ('a', 2)
            cur_str = last_str + cur_str * num   # 字符串拼接 a + c * 2 = acc
        else:
            cur_str += c     # 普通字符直接拼接到当前字符串

    return cur_str

print(decodeString("b3[a2[c]]"))  # 输出: "baccaccacc" （b acc acc acc）

"""
b [] 
3 [] b
[ [] b
a [('b', 3)] 
2 [('b', 3)] a
[ [('b', 3)] a
c [('b', 3), ('a', 2)] 
] [('b', 3), ('a', 2)] c     # 遇到第一个 ] 出栈 "('a', 2)] c" =  a + c * 2 = acc 
] [('b', 3)] acc             # 遇到第二个 ] 出栈 "[('b', 3)] acc" =  b + accc * 3 = baccaccacc
"""

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

# 06.移掉K位数字

402.移掉 K 位数字 (opens new window)
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小
请你以字符串形式返回这个最小的数字

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零

输入：num = "1432219", k = 3
输出："1219"

1
2
3
4
5
6

1、Python

遍历每个数字时，我们将其与栈顶数字比较
如果栈顶数字大于当前数字，并且我们还有机会移除数字（k > 0），则移除栈顶数字
这个过程确保我们逐步构建的数字尽可能小

class Solution:
    def removeKdigits(self, num, k):
        stack = []
        for digit in num:    # 构建单调递增的数字串
            while k > 0 and stack and stack[-1] > digit:   # k>0保证最多移除k个数
                stack.pop()
                k -= 1
            stack.append(digit)
        # 最终 stack = ['0', '0', '2', '2', '1', '9'], 移除首位1 和 43这三个字符
        if k > 0:
            # l=[1,2,3,4,5],  l[:-2]=[1, 2, 3]
            stack = stack[:-k]  # 如果 K > 0，删除末尾的 K 个字符
        return "".join(stack).lstrip('0') or "0"    # 抹去前导零，如果最终结果为空，则返回 "0"

print( Solution().removeKdigits("100224319", 3)) # 2219

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 07.基本计算器

224.基本计算器 (opens new window)
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值
s 由数字+-()空格 组成
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符

1、Python

用栈存储括号外的运算结果和符号（栈中这种 3+4+5+6 会直接算出结果存储到cur_res中）
遍历字符串，字符串根据字符串下面四种情况匹配：(+-)
① ( ：计算cur_res结果并将结果入栈，同时cur_res=0 sign=+
② 数字：计算cur_num当前数字（可能有多位）
③ +-: 计算cur_res 并设置sign=char cur_num=0
④ ): 遇到右括号证明匹配到了一个完整左右括号，出栈计算结果

class Solution:
    def calculate(self, s):
        stack = []                # 用栈存储括号外的运算结果和符号
        cur_res = 0               # 当前计算的累积结果
        cur_num = 0               # 当前正在处理的数字
        sign_map = {"+": 1, "-": -1}  # 使用字典来映射符号
        sign = "+"                # 当前符号，初始为 "+"

        for char in s:
            if char == '(':         # 1）入栈 计算cur_res结果 并将结果入栈
                stack.append(cur_res)                   # 将当前结果入栈保存
                stack.append(sign)
                cur_res = 0
                sign = "+"
            elif char.isdigit():    # 2）计算cur_num当前数字（可能有多位）
                cur_num = cur_num * 10 + int(char)  # 处理多位数字的情况
                
            elif char in sign_map:  # 3）计算cur_res
                cur_res += sign_map[sign] * cur_num     # 将当前数字和符号累加到结果中
                sign = char                             # 直接存储当前符号，稍后处理
                cur_num = 0

                
            elif char == ')':       # 4）出栈 括号内最后一个数字 + 累加栈顶值
                cur_res += sign_map[sign] * cur_num     # 处理括号内最后一个数字
                sign = stack.pop()
                # 将括号内结果乘以栈中的符号，并累加栈中的结果
                cur_res = stack.pop() + sign_map[sign] * cur_res
                cur_num = 0
            print(f"{char}\t{stack}\t{cur_res}")        # 打印当前字符、栈和累积结果

        return cur_res + sign_map[sign] * cur_num       # 10 处理最后一个数,并返回

print(Solution().calculate("(1+(2+(3+4+5+6)))"))

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

推演 "(1+(2+(3+4+5+6)))"

# print(f"{char}\t{stack}\t{cur_res}")
(	[0, '+']	0
1	[0, '+']	0
+	[0, '+']	1
(	[0, '+', 1, '+']	0
2	[0, '+', 1, '+']	0
+	[0, '+', 1, '+']	2
(	[0, '+', 1, '+', 2, '+']	0
3	[0, '+', 1, '+', 2, '+']	0
+	[0, '+', 1, '+', 2, '+']	3   # cur_res=3
4	[0, '+', 1, '+', 2, '+']	3
+	[0, '+', 1, '+', 2, '+']	7   # cur_res = cur_res+4 = 7
5	[0, '+', 1, '+', 2, '+']	7
+	[0, '+', 1, '+', 2, '+']	12  # cur_res = cur_res+5 = 12
6	[0, '+', 1, '+', 2, '+']	12
)	[0, '+', 1, '+']	20
)	[0, '+']	21
)	[]	21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#

# `② 回文`

# 11.回文数

9.回文数 (opens new window)
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数例如，121 是回文，而 123 不是

输入：x = 121
输出：true
输入：x = -121
输出：false

1
2
3
4

1、Python

class Solution:
    def isPalindrome(self, x):
        s = str(x)
        l, r = 0, len(s) - 1
        while l < r:
            if s[l] != s[r]:  # 只要有一处不匹配，就不是回文
                return False
            l += 1
            r -= 1
        return True  # 所有字符匹配，返回 True


print(Solution().isPalindrome(1221))  # True

1
2
3
4
5
6
7
8
9
10
11
12
13

# 12.最长回文串

409.最长回文串 (opens new window)
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串
在构造过程中，请注意区分大小写比如 "Aa" 不能当做一个回文字符串

输入:  "abccccdd
输出:  7
解释:  我们可以构造的最长的回文串是"dccaccd", 它的长度是 7

1
2
3

1、Python

如果字符已经在集合中出现，就移除它，否则添加进去
len(s) - len(odd_chars)计算的是可以形成的最长偶数长度的回文
如果集合中还有字符，那么可以再在中间添加一个字符构成奇数长度的回文

def longestStr(s):
    # 使用集合来记录字符的奇数次出现
    odd_chars = set()
    for char in s:
        if char in odd_chars:
            odd_chars.remove(char)
        else:
            odd_chars.add(char)
    
    # 如果有奇数字符，那么我们可以在回文的中心添加一个字符
    return len(s) - len(odd_chars) + (1 if odd_chars else 0)

# 示例用法
s = 'abcccccdd'
print(longestStr(s))  # 输出: 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 13.最长回文子串

5.最长回文子串 (opens new window)
给你一个字符串 s，找到 s 中最长的回文子串

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案

1
2
3

1、Python

本题最容易想到的一种方法应该就是 中心扩散法
从每一个位置出发，向两边扩散即可，遇到不是回文的时候结束

class Solution:
    def subscript(self, s, l, r):
        # 左指针大于等于0，右指针小于字符串长度，并且左右对称位置“值”相等，就继续循环
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - 1

    def longestString(self, s):
        start, end = 0, 0           # 最开始，初始化左右位置都为 0号位置
        for i in range(len(s)):
            l1, r1 = self.subscript(s, i, i)     # 以单个字符为中心（奇数长度回文）
            l2, r2 = self.subscript(s, i, i + 1) # 以两个字符为中心（偶数长度回文）
            
            if r1 - l1 > end - start:  # 更新最长回文子串的索引
                start, end = l1, r1
            if r2 - l2 > end - start:
                start, end = l2, r2
        return s[start: end + 1]

print(Solution().longestString('babad'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#

# `③ 数学`

# 21.二进制求和

67.二进制求和 (opens new window)
给你两个二进制字符串，返回它们的和（用二进制表示）
输入为非空字符串且只包含数字 1 和 0

输入: a = "11", b = "1"
输出: "100"
输入: a = "1010", b = "1011"
输出: "10101"

1
2
3
4

1、Python

def addBin(num1, num2):
    i, j = len(num1) - 1, len(num2) - 1  # 设定 i，j 两指针分别指向 num1，num2 尾部
    carry = 0    # 两数相加进位为0
    ret = ''     # 结果
    while i >= 0 or j >= 0:
        n1 = int(num1[i]) if i >= 0 else 0  # 获取 num1[i]，超出范围则视为 0
        n2 = int(num2[j]) if j >= 0 else 0
        tmp = n1 + n2 + carry      # 计算当前位的和
        ret = str(tmp % 2) + ret   # 取余 就是当前位的值，并加入字符串右面
        carry = tmp // 2           # 井位
        i, j = i - 1, j - 1        # 指针向右移动一位
    if carry:                  # 如果循环结束还存在井位，在头部添加进位 1
        ret = '1' + ret
    return ret


print(addBin('11', '10'))   # '101' =》 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 22.36进制加法

36进制加法 (opens new window) 头条补充题
36进制由0-9，a-z，共36个字符表示
要求按照加法规则计算出任意两个36进制正整数的和，如1b + 2x = 48 （解释：47+105=152）
要求：不允许使用先将36进制数字整体转为10进制，相加后再转回为36进制的做法

1、Python

使用两个字典，char_to_value 用于将字符映射到其对应的数值，value_to_char 用于将数值映射回字符
根据上面转换，计算方法和正常字符串相加基本一致，逐位相加 即可
处理进位和结果反转：
- 当循环结束时，可能会有一个进位剩余，如果有进位，我们会继续处理它
- 由于计算结果是从低位到高位生成的，最终需要将 res 列表反转并转换为字符串

class Solution:
    def __init__(self):
        #字符串转数字： {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5
        self.char_to_value = {ch: i for i, ch in enumerate("0123456789abcdefghijklmnopqrstuvwxyz")}
        #数字转字符串： 'u', 31: 'v', 32: 'w', 33: 'x', 34: 'y', 35: 'z'}
        self.value_to_char = {i: ch for i, ch in enumerate("0123456789abcdefghijklmnopqrstuvwxyz")}

    def addStrings(self, num1, num2):
        res = []
        i, j, carry = len(num1) - 1, len(num2) - 1, 0   # i 和 j 指向两个字符串的末尾，carry 表示进位

        while i >= 0 or j >= 0 or carry:
            # 取出当前位的字符并转换为数值
            n1 = self.char_to_value[num1[i]] if i >= 0 else 0
            n2 = self.char_to_value[num2[j]] if j >= 0 else 0
            tmp = n1 + n2 + carry                     # 计算当前位的和，包括进位
            res.append(self.value_to_char[tmp % 36])  # 当前位的值为 tmp % 36，找到对应的字符
            carry = tmp // 36                         # 更新进位值
            i -= 1
            j -= 1

        res.reverse()                 # 将结果列表反转并转换为字符串
        return ''.join(res)

print(Solution().addStrings("1b", "2x"))  # 输出："48"
print(Solution().addStrings("1234", "123"))  # 输出："1357"

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

# 23.字符串转换整数 (atoi)

8.字符串转换整数 (atoi) (opens new window)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数
跳过前导空格：忽略字符串开头的所有空格
处理符号：检查是否有符号字符（+ 或 -），并记录结果的符号
读取数字：从当前位置开始读取数字字符，并转换为整数
处理溢出：确保结果不会超出 32 位有符号整数的范围

1、Python

class Solution:
    def myAtoi(self, s):
        i = 0
        while i < len(s) and s[i] == ' ':     #1.跳过前导空格
            i += 1

        if i < len(s) and (s[i] == '+' or s[i] == '-'): #2.处理符号
            sign = -1 if s[i] == '-' else 1
            i += 1
        else:
            sign = 1

        res = 0
        while i < len(s) and s[i].isdigit():        #3.读取数字
            digit = int(s[i])
            if res > (2 ** 31 - 1 - digit) // 10:   # 检查是否会溢出
                return 2 ** 31 - 1 if sign == 1 else -2 ** 31

            res = res * 10 + digit
            i += 1

        return res * sign

print( Solution().myAtoi("   -123") )  # -123

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#

# `④ 其他`

# 31.最长公共前缀

14.最长公共前缀 (opens new window)
编写一个函数来查找字符串数组中的最长公共前缀
如果不存在公共前缀，返回空字符串 ""

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

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

1
2
3
4
5
6

1、Python

将第一个字符串设为初始的最长公共前缀 res
从第二个字符串开始，逐个与当前的 res 进行比较
通过字符逐一比较 res 和当前字符串，找到它们的公共前缀长度 l
如果找到公共前缀，则更新 res 为该公共前缀；如果没有公共前缀，直接返回空字符串

def longest(strs):
    res = strs[0]         # 初始化最长公共前缀 res 为第一个字符串
    for r in range(1, len(strs)):
        l = 0
        # 比较当前的 res（前缀）和 strs[r]（当前字符串），找到它们的公共前缀
        while l < len(res) and l < len(strs[r]):
            if res[l] != strs[r][l]:
                break
            l += 1
        if l == 0:      # 如果没有公共前缀，直接返回空字符串
            return ""
        res = strs[0][:l]  # 更新 res 为当前找到的公共前缀
    return res

print(longest(["flower", "flow", "flight"]))    # 输出: fl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 32.找出字符串中第一个匹配项的下标

28.找出字符串中第一个匹配项的下标 (opens new window)
给定一个 haystack 字符串和一个 needle字符串
在 haystack 字符串中找出needle字符串出现的第一个位置 (从0开始)
如果不存在，则返回 -1

# 示例 1:
输入: haystack  = "hello", needle = "ll"
输出: 2

# 示例 2:
输入: haystack  = "ababcababd", needleneedle = "ababd"
输出: -1

1
2
3
4
5
6
7

1、Python KMP 算法

KMP 算法用于在字符串 haystack 中查找 needle 的第一个匹配位置
它的核心是 LPS（Longest Prefix Suffix，最长前缀后缀）数组
- needle = "ababd"，最终 LPS 数组 lps = [0, 0, 1, 2, 0]
通过 LPS，我们可以在失配时高效地跳转，避免重复匹配，提高搜索效率

class Solution:`needle = "ababd"`，最终 `LPS` 数组 `lps = [0, 0, 1, 2, 0]`
    def strStr(self, haystack, needle):
        """ KMP 主算法，查找 `needle` 在 `haystack` 中的第一个匹配位置 """
        next_arr = self.build_next(needle)  # [0, 0, 1, 2, 0]
        i, j = 0, 0  # 主串和子串的指针

        while i < len(haystack):
            if haystack[i] == needle[j]:  # 字符匹配，两个指针都后移
                i += 1
                j += 1
            elif j > 0:    # 失配时，跳过部分匹配
                j = next_arr[j - 1]
            else:          # 第一个字符失配，主串指针后移
                i += 1

            if j == len(needle):  # 匹配成功
                return i - j

        return -1  # 没有匹配

    def build_next(self, needle):
        lps = [0]  # 初始化 LPS 数组，第一个字符的前后缀长度必定是 0
        j = 0      # 记录最长公共前后缀的长度
        i = 1      # `i` 从 1 开始（因为 `lps[0]` 必定为 0）

        while i < len(needle):
            if needle[i] == needle[j]:  # 如果当前字符和前缀字符匹配
                j += 1         # 公共前后缀长度加 1
                lps.append(j)  # 记录当前子串的 LPS 值
                i += 1         # 继续向后遍历
            else:              # 如果不匹配
                if j == 0:
                    lps.append(0) # 如果没有任何公共前后缀，直接记 0
                    i += 1        # 继续遍历模式串
                else:
                    # 关键：回退到 `j` 的前一个 LPS 位置，尝试更短的公共前后缀
                    j = lps[j - 1]
        return lps  # [0, 0, 1, 2, 0]

print(Solution().strStr("ababcababd", "ababd"))  # 输出: 5

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
38
39
40

LPS 数组的作用是：
- 对于 needle[0:i]，找到最长的 既是前缀又是后缀的子串长度（但不能是整个 needle[0:i] 本身）

示例：needle = "ababd"，最终 LPS 数组 lps = [0, 0, 1, 2, 0]

`i`	`needle[0:i]`	前缀集合（不含完整串）	后缀集合	最长匹配前后缀	`lps[i]`
0	A	—	—	无	0
1	AB	A	B	无	0
2	ABA	`A`, AB	BA, `A`	A	1
3	ABAB	A, `AB`, ABA	BAB, `AB`, B	AB	2
4	ABABD	A, AB, ABA, ABAB	D, BD, ABD, BABD	无	0

LPS 让 needle 在失配时，不回到 j=0，而是跳到已匹配前后缀的位置，避免重复匹配
并且主串i指针不回退，降低时间复杂度，从 O(n*m) 降到 O(n+m)

2、Python 暴力破解

暴力破解

def strStr(haystack, needle):
    L, n = len(needle), len(haystack)  # L短字符串长度，n长字符串长度
    for start in range(n - L + 1):
        if haystack[start: start + L] == needle:
            return start
    return -1

print( strStr( 'hello', 'll' ) )    # 2

1
2
3
4
5
6
7
8

# 33.字符串压缩

面试题 01.06. 字符串压缩 (opens new window)
字符串压缩，利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能
若“压缩”后的字符串没有变短，则返回原先的字符串
你可以假设字符串中只包含大小写英文字母（a至z）

 输入："aabcccccaaa"
 输出："a2b1c5a3"

 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长

1
2
3
4
5
6

1、Python

我们从左往右遍历字符串，用 ch记录当前要压缩的字符，cnt记录 ch出现的次数
如果当前枚举到的字符 s[i]等于ch，我们就更新 cnt的计数，即 cnt = cnt + 1
否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里，即 ans = ans + ch + cnt,完成对 ch字符的压缩
随后更新 ch为 s[i]，cnt 为 1，表示将压缩的字符更改为 s[i]
在遍历结束之后，我们就得到了压缩后的字符串ans，并将其长度与原串长度进行比较
如果长度没有变短，则返回原串，否则返回压缩后的字符串

def compressString(S):
    ch = S[0]      # ch记录当前要压缩的字符
    ans = ''       # ans拼接新字符串
    cnt = 0        # cnt记录 ch出现的次数
    for c in S:
        if c == ch:        # 当前枚举到的字符 s[i]等于ch，就加一
            cnt += 1
        else:              # 否则我们按题目要求将 ch以及cnt 更新到答案字符串ans 里
            ans += ch + str(cnt)  # `ans = ans + ch + cnt`,完成对 ch字符的压缩
            ch = c
            cnt = 1
    ans += ch + str(cnt)   # 跳出for循环后更新最后一部分
    return ans if len(ans) < len(S) else S

s = "aabcccccaaa"
print( compressString(s) )  # a2b1c5a3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 34.统计单词次数

统计指定文件中单词出现数量，并找到出现次数最多的前五个

import re
def wordCount(path,n):
	d = {}
	with open(path, encoding="utf-8") as f:
		data = f.read()
		# words = ['version', '3', 'services', .... ]
		words = [s.lower() for s in re.findall("\w+", data)]
		for word in words:
			d[word] = d.get(word, 0) + 1
	return sorted(d.items(), key=lambda item: item[1], reverse=True)[:n]

if __name__ == '__main__':
	pt = r'C:\tmp\drf_demo\book\models.py'
	most_common_5 = wordCount(pt,5)
	print(most_common_5)  # [('mysql', 5), ('root', 3), ('db', 3), ('environment', 2), ('3306', 2)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 35.无重复字符的最长子串

3.无重复字符的最长子串 (opens new window)
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度
- 以(a)bcabcbb 开始的最长字符串为 (abc)abcbb；
- 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
- 以 ab(c)abcbb开始的最长字符串为ab(cab)cbb

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3

1
2
3

1、Python

我们定义一个左右指针，初始化都指向0位置
右指针每次从左指针位置向右滑动，当出现重复值时结束while循环并重新计算最大值

def longestSubstring(s):
	set_ = set()           # 哈希集合，记录每个字符是否出现过
	n = len(s)
	res = 0                # 记录最大子串长度
	for l in range(n):
		r = l
		while r < n and s[r] not in set_:  # 字符串遍历完成或者出现重复字符串结束
			set_.add(s[r])
			r += 1                           # 不断地移动右指针
		set_ = set()
		res = max(res, r - l)
	return res

print(longestSubstring("abcabcbb"))  # 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14

上次更新: 2025/3/25 17:29:52

← 08.动态规划 21.链表→

11.字符串

# ① 栈（Stack）

# 01.有效的括号

# 02.最长有效括号

# 03.反转字符串中的单词 III

# 04.去除重复字母

# 05.字符串解码

# 06.移掉K位数字

# 07.基本计算器

#

# ② 回文

# 11.回文数

# 12.最长回文串

# 13.最长回文子串

#

# ③ 数学

# 21.二进制求和

# 22.36进制加法

# 23.字符串转换整数 (atoi)

#

# ④ 其他

# 31.最长公共前缀

# 32.找出字符串中第一个匹配项的下标

# 33.字符串压缩

# 34.统计单词次数

# 35.无重复字符的最长子串

# `① 栈（Stack）`

# `② 回文`

# `③ 数学`

# `④ 其他`