Anagram及相关算法题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const map = {}
    for (let str of strs) {
        const wordCnt = Array(26).fill(0)
        for (let c of str) {
            // str.charCodeAt(index) 是一个用来获取字符串中特定位置字符的 UTF-16编码数值 的方法，不传参时默认index=0
            wordCnt[c.charCodeAt() - 'a'.charCodeAt()]++
        }
        map[wordCnt] ? map[wordCnt].push(str) : map[wordCnt] = [str]
    }
    return Object.values(map)
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    const result = []
    const sLen = s.length
    const pLen = p.length
    const sWindowArr = new Array(26).fill(0)
    const pWindowArr = new Array(26).fill(0)

    const isWindowEqual = (m, n) => {
        for (let i = 0; i < 26; i++) {
            if (m[i] !== n[i]) {
                return false
            }
        }
        return true
    }

    // 第一个窗口
    for (let i = 0; i < pLen; i++) {
        sWindowArr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++
        pWindowArr[p.charCodeAt(i) - 'a'.charCodeAt(0)]++
    }
    if (isWindowEqual(sWindowArr, pWindowArr)) {
        result.push(0)
    }
    // 左出右进，定长滑动窗口
    for (let i = pLen; i < sLen; i++) {
        sWindowArr[s.charCodeAt(i - pLen) - 'a'.charCodeAt(0)]--
        sWindowArr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++
        if (isWindowEqual(sWindowArr, pWindowArr)) {
            result.push(i - pLen + 1)
        }
    }

    return result
};