介绍

回文字符串，就是正着读和倒着读都一样的字符串，比如说这样：'abccba'，回文字符串还有一个特性，单个字符串肯定回文，也就是说'aba'也是回文字符串；

根据这个定义，我们不难写出判断回文字符串的代码： :smiley:

1
2
3
4
5
6
function isPalindrome(str) {
    // 先反转字符串
    const reversedStr = str.split('').reverse().join('');
    // 判断反转前后是否相等
    return reversedStr === str;
}

也可以从回文字符串的对称性考虑（记住这个对称性，很重要）还可以这样写:

1
2
3
4
5
6
7
8
9
10
11
12
13
function isPalindrome(str) {
    if (!str) return;
    let len = str.length;
    let k = len - 1;    // 指针
    for (let i = 0; i < len / 2; i++) {
        if (i <= k && str[i] !== str[k]) {
            return false;
        }
        k--;
    }
    return true;
}

高频题

1.给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

一般看到回文字符串就要想起他的对称性，对称性要对应的想到双指针。

思路：

  1. 通过左右指针所指的元素是否相等来判断是否回文；
  2. 如果不等，分别左右指针先后跳过一位，对比是否相等；
  3. 如果还不等，那不满足回文字符串对称性，肯定就不是了；
  4. 如果相等，继续进行指针对比，如果接下来都对称了，且跳过次数不大于1则满足最多删除一个字符，能成为回文字符串；
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
function validPalindrome(str) {
    if (!str) return;
    let len = str.length;
    // j，k左右指针、count 记录跳过的次数、 flag是否回文
    let j = 0,
        k = len - 1,
        count = 0,
        flag = true;

    for (let i = 0; i < len; i++) {
        if (j > k) break;
        if (str[j] === str[k]) {
            j++;
            k--;
        } else if (str[j + 1] === str[k]) {
            // 左指针跳过一个
            j = j + 2;
            k--;
            count++;
            if (count > 1) return false;
        } else if (str[j] === str[k - 1]) {
            // 右指针跳过一个
            k = k - 2;
            j++;
            count++;
            if (count > 1) return false;
        } else {
            // 非回文字符串,直接跳出循环
            flag = false;
            break;
        }
    }

    return flag;
}

console.log(validPalindrome('abcdefgfedcba'));     // true
console.log(validPalindrome('a1bcdefgfedcba'));    // true
console.log(validPalindrome('a1bcdefgfe2dcba~'));  // false

性能优化：
在上面思路的第4条，如果有一次不等进行了跳过，就已经达到最多删除一个字符条件上限了，直接把还未对比的字符串当成一个整字符串判断是否是回文就行，如果回文则可以满足条件，不回文则不满足，没必要再做多余的循环：

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
41
42
43
function validPalindrome(s) {
    // 缓存字符串的长度
    const len = s.length

    // i、j分别为左右指针
    let i = 0,
        j = len - 1

    // 当左右指针均满足对称时，一起向中间前进
    while (i < j && s[i] === s[j]) {
        i++
        j--
    }

    // 尝试判断跳过左指针元素后字符串是否回文
    if (isPalindrome(i + 1, j)) {
        return true
    }
    // 尝试判断跳过右指针元素后字符串是否回文
    if (isPalindrome(i, j - 1)) {
        return true
    }

    // 工具方法，用于判断字符串是否回文
    function isPalindrome(st, ed) {
        while (st < ed) {
            if (s[st] !== s[ed]) {
                return false
            }
            st++
            ed--
        }
        return true
    }

    // 默认返回 false
    return false
};

console.log(validPalindrome('abcdefgfedcba')); // true
console.log(validPalindrome('a1bcdefgfedcba')); // true
console.log(validPalindrome('a1bcdefgfe2dcba~')); // false

2.字符串匹配问题

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。
. 可以表示任何一个字母。

示例: addWord(“bad”)
addWord(“dad”)
addWord(“mad”)
search(“pad”) -> false
search(“bad”) -> true
search(“.ad”) -> true
search(“b..”) -> true
说明:
你可以假设所有单词都是由小写字母 a-z 组成的。

思路：

  1. 要求既能添加，还能对添加的数据进行搜索，那肯定是要把添加的数组存起来，且最好是键值对存储，减少检索成本，这里我们使用Map;
  2. 这里为了降低查找时的复杂度，我们可以考虑以字符串的长度为 key，相同长度的字符串存在一个数组中，这样可以提高我们后续定位的效率。
  3. 还有一点是，search方法，既能完全匹配，还要能正则匹配，所以入参需要判断是普通字符串还是正则表达式；
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
41
42
43
44
45
46
47
48
49
50
51
52
53
// 构造函数
function WordDictionary() {
    this.words = new Map();
}

WordDictionary.prototype.addWord = function (str) {
    if (!str) return;
    let len = str.length;
    let val = this.words.get(len);
    if (val) {
        val.push(str);
        this.words.set(len, val);
    } else {
        this.words.set(len, [str]);
    }
}

WordDictionary.prototype.search = function (str) {

    if (!str) return;

    // 传入的字符串的长度找不到记录，则查询的字符串不存在
    let len = str.length;

    if (!this.words.get(len)) return false;
    let val = this.words.get(len);

    // 判断传入的是字符串还是正则
    if (!str.includes('.')) {
        return val.includes(str);
    }

    // 正则
    let reg = new RegExp(str);

    // 只要有一项满足就为true,
    // some方法，有一项满足条件的返回为true， 
    // every方法，每一项都要满足条件才返回true
    return val.some(item => reg.test(item));

}


const Words = new WordDictionary();

Words.addWord('dad');
Words.addWord('lala');
Words.addWord('abc');
console.log(Words.words);           // Map { 3 => [ 'dad', 'abc' ], 4 => [ 'lala' ] }
console.log(Words.search('l...'));  // true
console.log(Words.search('dad'));   // true
console.log(Words.search('a..'));   // true
console.log(Words.search('l'));     // false