Day3 - String Pre-Knowledge

Day3 - 字符串前置知识

1. 字符串介绍

字符串是一串字符组成的序列,跟数组类似,处理数组的一些方法同样适用于字符串.。

  • 查找字符串常用的数据结构有:

    • 前缀树

    • 后缀树

  • 常用的字符串算法:

    • KMP算法,在字符串匹配时特别高效。

2. 时间复杂度

字符串实际上就是一个字符数组,字符串操作和数组操作类似,所以复杂度也基本类似。

操作

时间复杂度

访问

O(1)

搜索

O(n)

插入

O(n)

删除

O(n)

3. 多个字符串

操作

时间复杂度

备注

查找子串

O(nm)

朴素的查找方式

字符串拼接

O(n+m)

字符串切片

O(m)

字符串分割(根据指定字符)

O(n+m)

去除字符串首尾空格

O(n)

4. 注意的问题

  • 字符串是否对大小写敏感

  • 是否只包含英文字符。

5. 边界的情况

  • 空字符串。

  • 字符串只包含一个或两个字符。

  • 字符串包含重复字符。

  • 字符串由非重复字符组成。

6. 常用的方法

6.1. 字符统计

统计字符串中字符出现的频率,最常见的方法是使用哈希表(C++中可以用数组模拟)。(有些语言内置了统计函数,比如Python,也可以直接使用。)

  • 如果需要进行字符统计,常见的错误是认为统计需要的空间复杂度为 O(n)

    • 但统计由小写母组成的字符串需要的空间复杂度是 O(1) 而不是 O(n)。这是因为小写的英文字母只有26个,26是一个常数。

6.2. 不含重复字符的字符串

可以通过26位掩码来表示字符串中包含哪些小写字母。

mask = 0
for c in word:
    mask |= (1 << (ord(c) - ord('a')))

如果要判断两个字符串中是否包含相同的字符,可以把两个字符串对应的26位掩码做与操作mask_a & mask_b,如果结果不为0,则说明两个字符串中包含相同的字符。

6.3. 相同字母异位词

相同字母异位词是一种文字转换或文字游戏。它是重新排列单词或短语的字母以产生新的单词或短语,并且只使用一次所有原始字母。

要确定两个字符串是否为相同字母异位词,有几种方法:

  • 对两个字符串排序会得到相同的两个字符串。整个过程需要 O(nlogn) 的时间复杂度和 O(log(n)) 的空间复杂度。

  • 素数映射,如果我们将每个字符映射到一个素数,并将映射后的数字相乘,那么相同字母异位词会得到相同的乘积(素数因子分解)。这需要 O(n) 的时间复杂度和 O(1) 的空间复杂度。(乘法交换律和不变原理)

  • 字符的频率统计也可以用来确定两个字符串是否为相同字母异位词。这同样需要 O(n) 的时间复杂度和 O(1) 的空间复杂度。

6.4. 回文串

回文串是一个字符串序列,从前往后读和从后往前读得到的结果是一致的,如momracecar

下面是判断字符串是否是回文串的方法:

  • 把字符串进行翻转,翻转后的字符串和翻转前的字符串保持一致,则说明这个字符串是回文串。

  • 在字符串的开始和结束处设置两个指针。将指针同时向中间移动直到它们重合,两个指针指向的字符始终保持一致,那么这个字符串就是回文串。

回文串中字符的顺序很重要,所以判断回文串的时候哈希表通常不适用。

计算字符串回文子串的数量时,常见的方法是中心扩散法,以字符串中的每个字符为中心,使用两个指针由中心向两边移动。回文串可以是偶数或奇数长度。对于回文串的中心位置,需要考虑中心包含两个字符和中心包含一个字符的情况。

  • 对于子字符串,一旦没有匹配,就可以提前终止。

  • 对于子序列,通常使用动态规划,因为会有重叠的子问题。

Last updated