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

编程技巧

转成字符数组来遍历

对于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个以内。

典型问题

变位词

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

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

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

典型问题

回文

典型问题

状态压缩

典型问题

其他

典型问题