稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

String Problems Archive

字符串即由字符组成的线性数组结构,可以理解为字符数组或者字符列表,但元素的集合是有限集合,通常是英文字符,数字和算术运算符号。可以说数组和列表的常见问题和技巧都可以应用于字符串,但因为是有限集合,所以又有一些独特的问题和技巧,今天就来总结一下。

编程技巧

转成字符数组来遍历

对于Java语言来说charAt(i)非常的慢,所以如果需要多次遍历,或者多次获利某个索引位置的字符,最好先转成字符数组toCharArray(),这样效率会高出很多。对于其他语言像Python3和Kotlin则没必要,因为本来就可以像常规数组(列表)一样遍历。

用桶代替哈希表

字符串的每个元素是有限集合,所以要尽可能的用桶来代替哈希表,每当需要对字符计数,或者做映射的时候,都可以先尝试用桶。 比如小写英文字母,就可以用一个长度为26的整数数组来计数,字符与索引的转化关系是ch-‘a’,同理可以扩展到大写ch-‘A’,甚至数字字符ch-‘0’。

字符与索引相互转化

前面提到了用桶,就是把字符转化为索引。反过来也是可行的。目标字符ch = (char) (i + ‘a’)就把索引转为小写,大写和数字字符也是同理的。

Java/C/C++

传统语言里面char相当于无符号整数,所以可以直接强行互转:

1
2
char ch = (char) (i + 'a');
int idx = ch - 'a'

Python3

大Python3中要用ord()和chr()来进行字符到整数的互转

1
2
idx = ord(ch) - ord('a')
ch = chr(idx + ord('a'))

Kotlin

因为Kotlin中没有所谓的基础类型,都是对象,所以就用对象提供的方法即可。字符转为整数用Char.code,要把数字字符转为对应字面的整数用Char.digitToInt,如:

1
2
3
val ch: Char = '3'
println("ch as int ${ch.code}, ch digit as int ${ch.digitToInt()}")
// ch as int 51, ch digit as int 3

如果是想转成其他进制的整数,可以传入基数作为参数,如:

1
2
val hexCh = 'F'
println("hex ch ${hexCh.digitToInt(16)}") // 15

因为是基于JVM的,所以字符也可以用于计算,比如idx = ch - ‘a’,这是完全没有问题的。

1
2
3
4
5
val a = 'a'
var idx = 'd' - a
val aidx = idx + 7
println("idx $idx, aidx to ch ${(aidx + 'a'.code).toChar()}")
//idx 3, aidx to ch k

反过来,整数转到字符,用Int.toChar()就可以了,会按ASCII的code值去转。另外,如果想转成数字字符用Character.forDigit(ch, radix):

1
2
val d = 8
println(" int to char ${d.toChar()}, to digit char ${Character.forDigit(d, 10)}")

字符数组/列表转为String

涉及字符的题目,一般需要转成字符数组处理后,再把字符数组转成字符串。

对于Java来说,String的构造方法支持传入char[]作为参数。

而Python3,其实就是字符列表转为字串,可以用join方法,这个方法是str提供的方法,用一个str当作分隔符来把一个列表连接起来:

1
2
chars = ['H', 'e', 'l', 'l', 'o']
''.join(chars) # "Hello"

同样,Kotlin中也有joinToString方法,它对数组和列表都支持,可以传入一个参数作为分隔符:

1
2
val chars = charArrayOf('H', 'e', 'l', 'l', 'o')
val res = chars.joinToString("")

压缩到位运算

如果字符集合特别有限,比如只有有限几个字符,或者只有小写,只有大写,这时可以更进一步的,用位运算来进行优化。小写字符只有26个,一个整数有32位可以用,完全够用。

当满足以下两个条件时就可以考虑用位运算来优化:仅涉及两个状态,有和没有;另外就是字符或者组合后的集合范围在32个以内。

典型问题

题目 题解 说明
451. 根据字符出现频率排序 题解
题解
题解

变位词

变位词是指对于一个字符串,把某几个字符位置换一下之后得到的字符串,与原串互为变位词。其实变位词不局限于字符串,对于任何一个线性列表来说,把某几个元素位置变一下就是互为变位词了。变位词有两大特点:字符集合是一样的,种类一样,频次也一样,但排列不一样。

基于它的特点,涉及变位词的问题,就变成了字符频次统计的问题了,如果两个字符串的字符频次一样,那么就互为变位词。另外的处理方式就是排序,因为只是排列不一样,所以按照同一规则排序后,两字符串就相同了,那么通过排序 来验证也可以可行的。具体处理时,要依据不同的条件来灵活选择具体的识别方式。

需要注意的是,当用频次统计法时,记得用桶而不是直接用哈希表。

典型问题

题目 题解 说明
49. 字母异位词分组 题解 排序法
题解
题解

回文

典型问题

题目 题解 说明
5. 最长回文子串 题解
题解
题解

状态压缩

典型问题

题目 题解 说明
187. 重复的DNA序列 题解
题解
题解

其他

典型问题

题目 题解 说明
题解
题解
题解

Comments