字符串（String）

字符串本身的数据结构并不复杂，同数组非常类似，没啥特别需要介绍的，就是题一般都不简单。

做题需要考虑：

有的字符串一定是 26 个字母，有的可能会包含空格。

注意事项 #

Golang #

注意：Go 的 for 循环得到的是 rune 类型的字符，需要进行转换。

func main() {
	a := "你好"
	for i, v := range a {
		fmt.Println(i, v, a[i], string(v))
	}
}
//0 20320 228 你
//3 22909 229 好

JavaScript #

注意下标，切片使用。有时需要将字符转换成 ASCII 码存到数组里，非常常用。

let s = "hello"

for (let i = 0; i < s.length; i++) {
    console.log(s[i], s.charCodeAt(i) - "a".charCodeAt());
}
//h 7
//e 4
//l 11
//l 11
//o 14

常见题型 #

变位词 #

剑指 Offer II 014. 字符串中的变位词

滑动窗口 #

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    if (s1.length > s2.length) {
        return false
    }
    let cnt1 = new Array(26).fill(0)
    let cnt2 = new Array(26).fill(0)
    let ac = 'a'.charCodeAt()

    for (let i = 0; i < s1.length; i ++) {
        cnt1[s1[i].charCodeAt() - ac] ++
        cnt2[s2[i].charCodeAt() - ac] ++
    }

    if (cnt1.toString() === cnt2.toString()) {
        return true
    }

    let n = s1.length
    for (let i = n; i < s2.length; i ++) {

        cnt2[s2[i].charCodeAt() - ac] ++
        cnt2[s2[i - n].charCodeAt() - ac]--

        if (cnt1.toString() === cnt2.toString()) {
            return true
        }

    }
    return false
};

类似的还有剑指 Offer II 015. 字符串中的所有变位词

双指针 #

var checkInclusion = function(s1, s2) {
    if (s1.length > s2.length) {
        return false
    }
    let cnt = new Array(26).fill(0)
    let ac = 'a'.charCodeAt()

    for (let i = 0; i < s1.length; i ++) {
        cnt[s1[i].charCodeAt() - ac] --
    }

    let n = s1.length
    let left = 0
    for (let i = 0; i < s2.length; i ++) {
        let x = s2[i].charCodeAt() - ac
        cnt[x] ++

        while(cnt[x] > 0) {
            cnt[s2[left].charCodeAt() - ac] --
            left ++
        }

        if (i - left + 1 === n) {
            return true
        }

    }
    return false
};

回文串 #

回文串首先可以考虑双指针。

剑指 Offer II 018. 有效的回文

子串问题 #

3. 无重复字符的最长子串

解法一：哈希表或 Set 集合

var lengthOfLongestSubstring = function (s) {
    let max = 0
    let map = new Map()
    let start = 0

    for (i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            start = map.get(s[i]) + 1
        }
        map.set(s[i], i)
        max = Math.max(max, i - start + 1)
    }
    return max
};

解法二：双指针

func lengthOfLongestSubstring(s string) int {
    left := 0
    right := 0
    ret := 0
    window := make(map[string]int)

    for (right < len(s)) {
        c := string(s[right])
        right ++
        window[c] ++
        for (window[c] > 1) {
            d := string(s[left])
            left ++
            window[d] --
        }
        ret = max(ret, right - left)
    }
    return ret
}

字符串相加 #

415. 字符串相加

字符串匹配算法 #

见字符串匹配

技巧总结 #

通过上面的例题，可以发现，大部分字符串的问题都是分析子串问题，然后解决办法一般是滑动窗口或者双指针。另外，有时还可能需要维护一个长度为 26 的数组（array）或者哈希表（map）或者集合（set）来统计每个字符出现的次数，这些方案的出场都是非常高频的。