本篇为Leetcode做题过程中字符串篇的总结和纠错等记录。

分类：

字符
回文串的定义
公共前缀
单词
字符串的反转
字符的统计
数字与字符串间转换
子序列
高精度运算
字符串变换
字符串匹配
中心拓展法

Python

要用Python做字符串类型的题，首先要了解Python内置了哪些处理字符串的函数或方法。

isalnum()

如果string至少有一个字符并且所有字符都是字母或数字则返回True，否则返回False。

filter()

用于过滤序列，过滤掉不符合条件的元素，返回由符合条件元素组成的新列表。该接收两个参数，第一个为函数，第二个为序列，序列的每个元素作为参数传递给函数进行判断，将返回True的元素放到新列表中。

join()

用于将序列中的元素以指定的字符连接生成一个新的字符串。用法为：

str.join(item) # 括号里只能有一个成员
# 例如：
','.join('abc')
# 输出结果为：'a,b,c'
''.join
# 将字符串中的所有大写字母转换为小写字母

str[::-1] 字符反转

strip()

去除字符串开头或者结尾的空格

get()

字典的方法，返回指定键的值。

get(key, value) value可选，当键不在字典中返回value。默认返回None。

统计字符串中字符的数量：for c in p: obj[c] = obj.get(c,0) + 1

Java

S.toCharArray()

将字符串转为对应的字符串数组

S.split(“-“)

将字符串按字符’-‘分隔

Integer.toBinaryString()

Integer类的toBinaryString()方法将整数参数的字符串表示形式返回为二进制基数为2的无符号整数。

Integer.parseInt()

parseInt()方法用于将字符串参数作为有符号的十进制整数进行解析。

String.join()

用给定的定界符连接所有元素，例如a是String[]，String.join("-",a);

计算字符串重新排列数

给定一个只包含大写英文字母的字符串S，要求你给出对S重新排列的所有不相同的排列数。

算法：

统计字符串中每个字符的出现次数。
计算字符总数的阶乘，这表示所有字符的排列数。
计算每个字符重复的次数的阶乘，并将这些阶乘相乘。
得到的结果就是不同排列的总数。

from collections import Counter
from math import factorial

def count_unique_permutations(s):
    # 统计字符出现次数
    counter = Counter(s)
    # 计算所有字符的排列数
    total_permutations = factorial(len(s))
    # 计算重复字符的阶乘并相乘
    for count in counter.values():
        total_permutations //= factorial(count)
    return total_permutations

counter.values()返回Counter对象中所有计数的值，即字符串中每个字符的出现次数。

字符的统计

1 2	for i in m: sum = m.count(i) # m中i的个数

Java charAt()方法

用于返回指定索引处的字符

反转字符串

交换两个值：

a,b = b,a

s[:] = s[::-1] 是切片赋值语法，表示用s[::-1]替换s中的元素，注意不能写成s = s[::-1]，因为s是形参，修改s不会影响函数外部传入的实参。注意这不是原地操作，需要O(n)的额外空间。

字符串算法篇

字符串匹配算法

KMP算法

例：28.找出字符串第一个匹配项的下标

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

示例 1：

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

示例 2：

1
2
3

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

提示：

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

参考来源：宫水三叶 https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/

奇乐编程学院 https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.337.search-card.all.click&vd_source=619ca0a91236fa2e514bd44a58491205

KMP算法是一个快速查找匹配串的算法，作用：快速在原字符串中找到匹配字符串

在朴素解法O(m*n)的基础上将复杂度提高到仅有O(m+n)。核心：KMP算法能在[非完全匹配]的过程中提取到有效信息进行复用，以减少[重复匹配]的消耗。

朴素匹配的逻辑：将原串的指针移动到本次[发起点]的下一个位置，匹配串的指针移动到起始位置；尝试匹配，发现对不上，原串的指针会一直往后移动，直到能够与匹配串对上位置。

所以朴素匹配的复杂度是O(m*n)

KMP匹配过程：

1、匹配串检查之前已经匹配成功的部分中是否存在相同的前缀和后缀，如果存在，则跳转到前缀的下一个位置继续往下匹配

2、跳转后尝试匹配，发现两个指针的字符对不上，并且匹配串指针前面不存在相同的前缀和后缀，这时候就回到匹配串的起始位置重新开始

KMP比朴素解法更快的原因：

KMP利用已匹配部分中相同的前缀和后缀来加速下一次的匹配
KMP的原串指针不进行回溯，没有朴素匹配中回到下一个发起点的过程

可以优化的部分只能是 检查已匹配部分的相同前缀和后缀 这一过程。检查前缀和后缀的目的其实是为了确定匹配串中的下一段开始匹配的位置。

对于匹配串的任意一个位置，由该位置发起的下一个匹配点位置其实与原串无关。

预处理得到next数组，数组中每个位置的值就是该下标应该跳转的目标位置（next点）

std::vector<int> KMP(const std::string &text, const std::string &pattern) {
    int n = text.size(), m = pattern.size();
    std::vector<int> next(m, 0);
    std::vector<int> matches;

    for (int i = 1; i < m; i++) {
        int j = next[i - 1];
        while (j > 0 && pattern[i] != pattern[j])
            j = next[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        next[i] = j;
    }

    int i = 0, j = 0;
    while (i < n) {
        while (j > 0 && text[i] != pattern[j])
            j = next[j - 1];
        if (text[i] == pattern[j])
            j++;
        if (j == m) {
            matches.push_back(i - j + 1);
            j = next[m - 1];
        }
        i++;
    }
    return matches;
}

def kmp_search(string, patt):
    next = build_next(patt) # 构建next数组
    
    i = 0 # 主串指针
    j = 0 # 子串指针
    while i < len(string):
        if string[i] == patt[j]: # 字符匹配，指针后移
        	i += 1
            j += 1
        elif j > 0 : # 字符失配，根据next跳过子串前面的一些字符
            j = next[j - 1]
        else: # 子串第一个字符就失配
            i += 1
        if j == len(patt): #匹配成功
            return i - j # 返回匹配的起始位置

时间复杂度为O(n)，n代表主串的长度

next数组的构建：

所以next数组的本质就是寻找子串中相同前后缀的长度，并且一定是最长的前后缀

def build_next(patt):
    """
    计算Next数组
    """
    next = [0]
    prefix_len = 0 #当前共同前后缀的长度
    i = 1
    while i < len(patt):
        if patt[prefix_len] == patt[i]: # 下一个字符依然相同，可以构成一个更长的前后缀
            prefix_len += 1
            next.append(prefix_len)
            i += 1
        else: # 下一个字符不同
            if prefix_len == 0: # 不存在更短的前后缀
                next.append(0)
                i += 1
            else:
                prefix_len = next[prefix_len - 1] # 查看其中是否存在更短的前后缀
    return next

计算Next数组的本质还是通过已经掌握的信息来规避重复的运算，和动态规划的思想很像

Miraisen

leetcode字符串篇