字符串

回文

判断一个字符串是不是回文

对撞指针法 双指针从 2 边开始遍历，不一样则不是回文

function isPalindrome(str) {
    let left = 0,
        right = str.length - 1;
    while (left < right) {
        if (str[left] !== str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

反转字符串法 反转字符串法是一种简单直接的方法，它先将字符串反转，再与原字符串进行比较。

function isPalindrome(str) {
    const reversed = str.split('').reverse().join('');
    return str === reversed;
}

递归法 递归法是一种比较巧妙的方法，它利用递归函数在字符串中依次比较首尾字符是否相等。

function isPalindrome(str) {
    if (str.length <= 1) {
        return true;
    }
    if (str[0] !== str[str.length - 1]) {
        return false;
    }
    return isPalindrome(str.slice(1, -1));
}

// 借助辅助函数，无需拷贝字符串开销
function isPalindrome(str) {
    return helper(0, str.length - 1);

    function helper(start, end) {
        if (end - start <= 1) {
            return true;
        }
        if (str[start] !== str[end]) {
            return false;
        }
        return helper(start + 1, end - 1);
    }
}

中心扩展法

function isPalindrome(s) {
    const len = s.length;
    for (let i = 0; i < len / 2; i++) {
        if (s[i] !== s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

字典树

通用 通过 hash 表存储

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let c = word[i];
            if (!node.children.has(c)) {
                node.children.set(c, new TrieNode());
            }
            node = node.children.get(c);
        }
        node.isEnd = true;
    }

    search(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let c = word[i];
            if (!node.children.has(c)) {
                return false;
            }
            node = node.children.get(c);
        }
        return node.isEnd;
    }
}

数组存储

仅限于只包含小写字母 a-z 的字符串。 word[i].charCodeAt(0) - 97 是通过字符的编码，算出在 26 个小写字母中，该字母的 index

class TrieNode {
    constructor() {
        this.children = new Array(26).fill('');
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let index = word[i].charCodeAt(0) - 97;
            if (!node.children[index]) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    search(word) {
        let node = this.root;
        for (let i = 0; i < word.length; i++) {
            let index = word[i].charCodeAt(0) - 97;
            if (!node.children[index]) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEnd;
    }
}

214. 最短回文串

暴力解法

Javascript

const shortestPalindrome = s => {
    const len = s.length;
    const rev_s = s.split('').reverse().join('');
    for (let i = len; i >= 0; i--) {
        if (s.substring(0, i) == rev_s.substring(len - i)) {
            return rev_s.substring(0, len - i) + s;
        }
    }
};

KMP

28. 找出字符串中第一个匹配项的下标

暴力解法

时间复杂度 O(n^2)

Javascript

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    const len = needle.length;
    const rowLen = haystack.length;
    for (let i = 0; i + len - 1 < rowLen; i++) {
        // console.log(haystack.substring(i,len+i) , needle);
        if (haystack.substring(i, len + i) === needle) {
            return i;
        }
    }
    return -1;
};

336. 回文对

20. 有效的括号

辅助栈

Javascript

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    if (s.length <= 1) return false;
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        if (['(', '{', '['].includes(s[i])) {
            stack.push(s[i]);
        } else {
            if (stack.length <= 0) return false;
            const item = stack.pop();
            if (item === '(' && s[i] !== ')') {
                return false;
            }
            if (item === '{' && s[i] !== '}') {
                return false;
            }
            if (item === '[' && s[i] !== ']') {
                return false;
            }
        }
    }
    return stack.length === 0;
};

31. 下一个排列

Javascript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    reverse(nums, i + 1, nums.length - 1);

    function reverse(nums, start, end) {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    }
};

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

暴力解法

details

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let maxLength = 0;
    // Generate all substrings and check for unique characters
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            let substring = s.slice(i, j);
            if (new Set(substring).size === substring.length) {
                maxLength = Math.max(maxLength, substring.length);
            }
        }
    }

    return maxLength;
};

滑动窗口

Javascript

/**
 *
 * @param {string} s
 * @returns {number}
 */
var lengthOfLongestSubstring = function (s) {
    const len = s.length;
    if (s.length <= 1) return len;
    const set = new Set();

    let ans = 0;

    let left = 0;
    let right = 0;
    while (right < len) {
        const char = s[right];
        right++;

        while (set.has(char)) {
            const char = s[left];
            left++;
            set.delete(char);
        }

        ans = Math.max(ans, right - left);
        set.add(char);
    }
    return ans;
};

1616. 分割两个字符串得到回文串

暴力解法

从 0 开始划分字符串。判断划分出来的字符串是否是回文。

时间复杂度 O(n^2) 空间复杂度 O(1)

Javascript

/**
 * @param {string} a
 * @param {string} b
 * @return {boolean}
 */
var checkPalindromeFormation = function (a, b) {
    const len = a.length;
    if (len === 1) return true;
    for (let i = 0; i < len; i++) {
        if (isPalindrome(a.slice(0, i) + b.slice(i)) || isPalindrome(b.slice(0, i) + a.slice(i))) {
            return true;
        }
    }
    return false;

    function isPalindrome(str) {
        const len = str.length;
        for (let i = 0; i < len / 2; i++) {
            if (str[i] !== str[len - 1 - i]) {
                return false;
            }
        }
        return true;
    }
};

双指针

如果a[i] === b[len-i]就可以 不用判断了。减少重复判断

Javascript

/**
 * @param {string} a
 * @param {string} b
 * @return {boolean}
 */
var checkPalindromeFormation = function (a, b) {
    return check(a, b) || check(b, a);

    function check(a, b) {
        const len = a.length;

        let left = 0,
            right = len - 1;
        while (left < right && a[left] === b[right]) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        }
        return isPalindrome(a, left, right) || isPalindrome(b, left, right);
    }

    function isPalindrome(str, left, right) {
        while (left < right) {
            if (str[left] !== str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

1625. 执行操作后字典序最小的字符串

失败的尝试

Javascript

/**
 * @param {string} s
 * @param {number} a
 * @param {number} b
 * @return {string}
 */
var findLexSmallestString = function (s, a, b) {
    let cur = s,
        len = s.length;
    console.log('raw', cur, a, b);

    while (true) {
        let smaller = cur;
        let i = 0;
        while (i < len) {
            let reverse = cur.slice(-b) + cur.slice(0, len - b);
            smaller = smallerThen(reverse, smaller) ? reverse : smaller;
            console.log('smaller', smaller, reverse);
            cur = reverse;
            i++;
        }
        let next = addA(smaller, a);
        console.log('next', next);
        if (smallerThen(next, cur)) {
            cur = next;
        } else {
            break;
        }
    }
    return cur;

    function addA(str, a) {
        let len = str.length,
            i = 1,
            cur = str;
        while (i < len) {
            let num = cur.charAt(i) - 0,
                sum = num + a;
            sum = sum > 9 ? sum % 10 : sum;
            cur = cur.slice(0, i) + sum + cur.slice(i + 1);
            i += 2;
        }
        return cur;
    }

    function smallerThen(a, b) {
        let i = 0,
            len = a.length;

        while (i < len) {
            let charA = a.charCodeAt(i),
                charB = b.charCodeAt(i);
            if (charA < charB) {
                return true;
            } else if (charA > charB) {
                return false;
            }
            i++;
        }
        return false;
    }
};

console.log(findLexSmallestString('43987654', 7, 3));
// console.log(findLexSmallestString('74', 5, 1));
// console.log(findLexSmallestString('74', 5, 1));

搞了一个上午没搞出来。最后把答案粘上去了

Javascript 官方答案

var findLexSmallestString = function (s, a, b) {
    const n = s.length;
    let res = s;
    s = s + s;
    const g = gcd(b, n);

    for (let i = 0; i < n; i += g) {
        const t = [...s.slice(i, i + n)];
        add(t, n, a, 1);
        if (b % 2 !== 0) {
            add(t, n, a, 0);
        }
        const tStr = t.join('');
        if (tStr < res) {
            res = tStr;
        }
    }
    return res;
};

const add = (t, n, a, start) => {
    let minVal = 10,
        times = 0;
    for (let i = 0; i < 10; i++) {
        const added = (t[start].charCodeAt() - '0'.charCodeAt() + i * a) % 10;
        if (added < minVal) {
            minVal = added;
            times = i;
        }
    }
    for (let i = start; i < n; i += 2) {
        t[i] = String.fromCharCode('0'.charCodeAt() + ((t[i].charCodeAt() - '0'.charCodeAt() + times * a) % 10));
    }
};

const gcd = (num1, num2) => {
    while (num2 !== 0) {
        const temp = num1;
        num1 = num2;
        num2 = temp % num2;
    }
    return num1;
};

1032. 字符流

暴力解法

把后缀 存到一张 hash 表。去 hash 表查找是否存在以 letter 结尾的后缀。(超时了 ❌)

Javascript

/**
 * @param {string[]} words
 */
var StreamChecker = function (words) {
    const map = new Map();
    this.queryStr = '';
    words.forEach(val => {
        map.set(val, 1);
    });
    this.map = map;
};

/**
 * @param {character} letter
 * @return {boolean}
 */
StreamChecker.prototype.query = function (letter) {
    this.queryStr += letter;
    let right = this.queryStr.length - 1;
    while (right >= 0) {
        if (this.map.has(this.queryStr.slice(right))) {
            return true;
        }
        right--;
    }

    return false;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * var obj = new StreamChecker(words)
 * var param_1 = obj.query(letter)
 */

优化一下 （通过了 ✅）

Javascript

/**
 * @param {string[]} words
 */
var StreamChecker = function (words) {
    this.queryStr = '';
    this.words = words;
};

/**
 * @param {character} letter
 * @return {boolean}
 */
StreamChecker.prototype.query = function (letter) {
    this.queryStr += letter;
    for (let word of this.words) {
        // 最后一个字符相等
        let last = word.length - 1;
        let letterLast = this.queryStr.length - 1;
        while (word[last] === this.queryStr[letterLast] && last >= 0 && letterLast >= 0) {
            last--;
            letterLast--;
        }
        if (last === -1) {
            return true;
        }
    }
    return false;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * var obj = new StreamChecker(words)
 * var param_1 = obj.query(letter)
 */

字典树

时间复杂度： 初始化操作的时间复杂度为 O(mn)，其中 m 是字符串数组中字符串的平均长度，n 是字符串数组中字符串的个数。 query 操作的时间复杂度为 O(m)，其中 m 是当前字符流中字符的个数。 空间复杂度： 字典树的空间复杂度为 O(mn)，其中 m 是字符串数组中字符串的平均长度，n 是字符串数组中字符串的个数。 StringBuilder 的空间复杂度为 O(m)，其中 m 是当前字符流中字符的个数。

Javascript

class TrieNode {
    constructor() {
        this.isEnd = false;
        this.children = new Array(26).fill(null);
    }
}

/**
 * @param {string[]} words
 */
var StreamChecker = function (words) {
    this.root = new TrieNode();
    this.sb = '';
    // 将所有字符串插入到字典树中
    for (let word of words) {
        let node = this.root;
        for (let i = word.length - 1; i >= 0; i--) {
            // 计算出 index  a 的charcode 是 97
            let idx = word.charCodeAt(i) - 97;
            if (!node.children[idx]) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
};

/**
 * @param {character} letter
 * @return {boolean}
 */
StreamChecker.prototype.query = function (letter) {
    this.sb += letter;
    let node = this.root;
    // 从根节点开始往下遍历字典树
    for (let i = this.sb.length - 1; i >= 0 && node; i--) {
        let idx = this.sb.charCodeAt(i) - 97;
        node = node.children[idx];
        if (node && node.isEnd) {
            return true;
        }
    }
    return false;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * var obj = new StreamChecker(words)
 * var param_1 = obj.query(letter)
 */

1574. 删除最短的子数组使剩余数组有序

双指针

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfShortestSubarray = function (nums) {
    const n = nums.length;
    let l = 0,
        r = n - 1;
    // 找到最右侧的降序子数组
    while (l < n - 1 && nums[l] <= nums[l + 1]) {
        l++;
    }
    if (l === n - 1) {
        // 数组已经有序
        return 0;
    }
    // 找到最左侧的降序子数组
    while (r > 0 && nums[r] >= nums[r - 1]) {
        r--;
    }
    let ans = Math.min(n - l - 1, r);

    let i = 0,
        j = r;
    while (i <= l && j < n) {
        if (nums[i] <= nums[j]) {
            ans = Math.min(ans, j - i - 1);
            i++;
        } else {
            j++;
        }
    }
    return ans;
};

1638. 统计只差一个字符的子串数目

双指针

题目分析 首先，我们可以先将 s 中的每个非空子串都枚举出来，然后将每个子串的每个字符都分别替换成 a-z 中的字符，并判断是否等于 t。这种做法时间复杂度为 O(n^3 * 26)，无法通过本题。 其次，我们考虑优化上述做法。我们可以将枚举子串和替换字符的过程合并起来，用一个双指针分别指向 s 和 t，当 s[i] != t[j] 时，我们可以将 i 和 j 分别右移一位，这样就可以快速地找到 s 和 t 中恰好只有一个字符不同的所有子字符串对。时间复杂度为 O(n^2)。

Javascript

function countSubstrings(s, t) {
    let res = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = 0; j < t.length; j++) {
            let diff = 0;
            for (let k = 0; i + k < s.length && j + k < t.length; k++) {
                if (s[i + k] !== t[j + k]) {
                    diff++;
                    if (diff > 1) break;
                }
                if (diff === 1) res++;
            }
        }
    }
    return res;
}