字符串即由字符组成的线性数组结构,可以理解为字符数组或者字符列表,但元素的集合是有限集合,通常是英文字符,数字和算术运算符号。可以说数组和列表的常见问题和技巧都可以应用于字符串,但因为是有限集合,所以又有一些独特的问题和技巧,今天就来总结一下。
编程技巧
转成字符数组来遍历
对于Java语言来说charAt(i)非常的慢,所以如果需要多次遍历,或者多次获利某个索引位置的字符,最好先转成字符数组toCharArray(),这样效率会高出很多。对于其他语言像Python3和Kotlin则没必要,因为本来就可以像常规数组(列表)一样遍历。
用桶代替哈希表
字符串的每个元素是有限集合,所以要尽可能的用桶来代替哈希表,每当需要对字符计数,或者做映射的时候,都可以先尝试用桶。 比如小写英文字母,就可以用一个长度为26的整数数组来计数,字符与索引的转化关系是ch-‘a’,同理可以扩展到大写ch-‘A’,甚至数字字符ch-‘0’。
字符与索引相互转化
前面提到了用桶,就是把字符转化为索引。反过来也是可行的。目标字符ch = (char) (i + ‘a’)就把索引转为小写,大写和数字字符也是同理的。
Java/C/C++
传统语言里面char相当于无符号整数,所以可以直接强行互转:
1 2 |
|
Python3
大Python3中要用ord()和chr()来进行字符到整数的互转
1 2 |
|
Kotlin
因为Kotlin中没有所谓的基础类型,都是对象,所以就用对象提供的方法即可。字符转为整数用Char.code,要把数字字符转为对应字面的整数用Char.digitToInt,如:
1 2 3 |
|
如果是想转成其他进制的整数,可以传入基数作为参数,如:
1 2 |
|
因为是基于JVM的,所以字符也可以用于计算,比如idx = ch - ‘a’,这是完全没有问题的。
1 2 3 4 5 |
|
反过来,整数转到字符,用Int.toChar()就可以了,会按ASCII的code值去转。另外,如果想转成数字字符用Character.forDigit(ch, radix):
1 2 |
|
字符数组/列表转为String
涉及字符的题目,一般需要转成字符数组处理后,再把字符数组转成字符串。
对于Java来说,String的构造方法支持传入char[]作为参数。
而Python3,其实就是字符列表转为字串,可以用join方法,这个方法是str提供的方法,用一个str当作分隔符来把一个列表连接起来:
1 2 |
|
同样,Kotlin中也有joinToString方法,它对数组和列表都支持,可以传入一个参数作为分隔符:
1 2 |
|
压缩到位运算
如果字符集合特别有限,比如只有有限几个字符,或者只有小写,只有大写,这时可以更进一步的,用位运算来进行优化。小写字符只有26个,一个整数有32位可以用,完全够用。
当满足以下两个条件时就可以考虑用位运算来优化:仅涉及两个状态,有和没有;另外就是字符或者组合后的集合范围在32个以内。
典型问题
题目 | 题解 | 说明 |
---|---|---|
451. 根据字符出现频率排序 | 题解 | |
题解 | ||
题解 |
变位词
变位词是指对于一个字符串,把某几个字符位置换一下之后得到的字符串,与原串互为变位词。其实变位词不局限于字符串,对于任何一个线性列表来说,把某几个元素位置变一下就是互为变位词了。变位词有两大特点:字符集合是一样的,种类一样,频次也一样,但排列不一样。
基于它的特点,涉及变位词的问题,就变成了字符频次统计的问题了,如果两个字符串的字符频次一样,那么就互为变位词。另外的处理方式就是排序,因为只是排列不一样,所以按照同一规则排序后,两字符串就相同了,那么通过排序 来验证也可以可行的。具体处理时,要依据不同的条件来灵活选择具体的识别方式。
需要注意的是,当用频次统计法时,记得用桶而不是直接用哈希表。
典型问题
题目 | 题解 | 说明 |
---|---|---|
49. 字母异位词分组 | 题解 | 排序法 |
题解 | ||
题解 |
回文
典型问题
题目 | 题解 | 说明 |
---|---|---|
5. 最长回文子串 | 题解 | |
题解 | ||
题解 |
状态压缩
典型问题
题目 | 题解 | 说明 |
---|---|---|
187. 重复的DNA序列 | 题解 | |
题解 | ||
题解 |
其他
典型问题
题目 | 题解 | 说明 |
---|---|---|
题解 | ||
题解 | ||
题解 |