97 篇博文 含有标签「字符串」

1、题干​

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

示例 1：

输入：s = "YazaAay"
输出："aAa"
解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例 2：

输入：s = "Bb"
输出："Bb"
解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例 3：

输入：s = "c"
输出：""
解释：没有美好子字符串。

示例 4：

输入：s = "dDzeE"
输出："dD"
解释："dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。

提示：

• 1 <= s.length <= 100
• s 只包含大写和小写英文字母。

2、解题思路​

由题意可知美好子串中不会单独存在大写或小写字母，因此可以在单独的大写或小写字母处断开字符串，对拆分出来的左右子串进行递归查找，直到子串成为美好子串。

3、代码​

var longestNiceSubstring = function (s) {
    for (let i = 0; i < s.length; i++) {
        const c = s[i].charCodeAt(0) < 91 ? s[i].toLowerCase() : s[i].toUpperCase();
        if (s.includes(c)) continue;
        const s1 = longestNiceSubstring(s.slice(0, i));
        const s2 = longestNiceSubstring(s.slice(i + 1));
        return s1.length >= s2.length ? s1 : s2;
    }
    return s;
};

4、执行结果​

1、题干​

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

• MagicDictionary() 初始化对象
• void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
• bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• dictionary[i] 仅由小写英文字母组成
• dictionary 中的所有字符串 互不相同
• 1 <= searchWord.length <= 100
• searchWord 仅由小写英文字母组成
• buildDict 仅在 search 之前调用一次
• 最多调用 100 次 search

2、解法1-字符串比较​

数组存储字典，查找时直接进行字符串比较，如果不匹配的字符数量为1返回true，否则继续查找直至结束返回false

3、代码​

var MagicDictionary = function () {
    this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }

    return false;
};

4、执行结果​

5、解法2-哈希表​

哈希表存储字典，查找时对源字符串的每一位做替换，若替换后哈希表存在该字符串则返回true，否则继续查找直至结束返回false

6、代码​

var MagicDictionary = function () {
    this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < searchWord.length; i++) {
        const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
        for (let j = 97; j < 123; j++) {
            const c = String.fromCharCode(j);
            if (c === searchWord[i]) continue;
            if (this.dict.has(pre + c + post)) return true;
        }
    }

    return false;
};

7、执行结果​

• 执行用时: 860 ms
• 内存消耗: 48.3 MB

1、题干​

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

• MagicDictionary() 初始化对象
• void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
• bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

解释
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False

提示：

• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• dictionary[i] 仅由小写英文字母组成
• dictionary 中的所有字符串 互不相同
• 1 <= searchWord.length <= 100
• searchWord 仅由小写英文字母组成
• buildDict 仅在 search 之前调用一次
• 最多调用 100 次 search

2、解法1-字符串比较​

数组存储字典，查找时直接进行字符串比较，如果不匹配的字符数量为1返回true，否则继续查找直至结束返回false

3、代码​

var MagicDictionary = function () {
    this.dict = [];
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }

    return false;
};

4、执行结果​

5、解法2-哈希表​

哈希表存储字典，查找时对源字符串的每一位做替换，若替换后哈希表存在该字符串则返回true，否则继续查找直至结束返回false

6、代码​

var MagicDictionary = function () {
    this.dict = new Set();
};

MagicDictionary.prototype.buildDict = function (dictionary) {
    for (const w of dictionary) this.dict.add(w);
};

MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < searchWord.length; i++) {
        const pre = searchWord.slice(0, i), post = searchWord.slice(i + 1);
        for (let j = 97; j < 123; j++) {
            const c = String.fromCharCode(j);
            if (c === searchWord[i]) continue;
            if (this.dict.has(pre + c + post)) return true;
        }
    }

    return false;
};

7、执行结果​

• 执行用时: 860 ms
• 内存消耗: 48.3 MB

1、题干​

句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和 ','）以及空格（' '）组成。每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' ' 分隔。

如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：

• 仅由小写字母、连字符和/或标点（不含数字）组成。
• 至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
• 至多一个 标点符号。如果存在，标点符号应当位于 token 的 末尾 。

这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。

给你一个字符串 sentence ，请你找出并返回 sentence 中 有效单词的数目 。

示例 1：

输入：sentence = "cat and  dog"
输出：3
解释：句子中的有效单词是 "cat"、"and" 和 "dog"

示例 2：

输入：sentence = "!this  1-s b8d!"
输出：0
解释：句子中没有有效单词
"!this" 不是有效单词，因为它以一个标点开头
"1-s" 和 "b8d" 也不是有效单词，因为它们都包含数字

示例 3：

输入：sentence = "alice and  bob are playing stone-game10"
输出：5
解释：句子中的有效单词是 "alice"、"and"、"bob"、"are" 和 "playing"
"stone-game10" 不是有效单词，因为它含有数字

提示：

• 1 <= sentence.length <= 1000
• sentence 由小写英文字母、数字（0-9）、以及字符（' '、'-'、'!'、'.' 和 ','）组成
• 句子中至少有 1 个 token

2、解题思路​

终于轮到正则选手出场

看下面内容之前需要一些正则基础

正则说明 ：

• 完整正则表达式：/^([,.!]|[a-z]+(-[a-z]+)?[,.!]?)$/
• 其中用 () 和 | 把正则中间部分分成两种情况，实际可以当成两个正则：/^[,.!]$/ 与 /^[a-z]+(-[a-z]+)?[,.!]?$/
• 要匹配完整的token：用 ^ 表示匹配到字符串起始位置，用 $ 表示匹配到字符串末尾
• token只有1个标点符号，即第一种情况 /^[,.!]$/，表示整个字符串是3个标点中任意1个
• token有字母的情况下，即第二种情况 /^[a-z]+(-[a-z]+)?[,.!]?$/，一定是1个或多个字母开头即 ^[a-z]+，后面可能有连字符 - 和字母即 (-[a-z]+)?，末尾可能有标点即 [,.!]?$

3、代码​

var countValidWords = function (sentence) {
    return sentence.split(' ').filter(w => /^([,.!]|[a-z]+(-[a-z]+)?[,.!]?)$/.test(w)).length;
};

4、执行结果​

• 执行用时: 76 ms
• 内存消耗: 39.4 MB

1、题干​

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

2、解法1-暴力解法​

双指针 i 和 j 枚举所有子串的起点和终点，遍历 i 和 j 区间段内的字符判断其是否回文。

这种方式时间复杂度是 $O(n^3)$，复杂度太高，如果数据量再大点可能会超时。其中双指针枚举的时间复杂度是 $O(n^2)$，回文判断的时间复杂度是 $O(n)$。解法2就是在此基础上优化了回文判断的复杂度。

3、代码​

var countSubstrings = function (s) {
    function isPal(s, l, r) {
        for (let i = l; i < (l + r) / 2; i++) {
            if (s[i] !== s[l + r - i - 1]) return false;
        }
        return true
    }

    let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            if (isPal(s, i, j)) count++;
        }
    }

    return count;
};

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(1)$

5、执行结果​

• 执行用时: 308 ms
• 内存消耗: 38.4 MB

6、解法2-双指针​

该解法是解法1的优化版本。先使用双指针 i 和 j 枚举所有子串的起点和终点，同时分别按顺序和逆序累加所有遍历过的字符得到字符串 s1 和 s2，判断是否回文只需对 s1 和 s2 判等即可。这里将回文判断的时间复杂度从 $O(n)$ 优化到 $O(1)$，但整体空间复杂度从 $O(1)$ 升到 $O(n)$，算是空间换时间。

7、代码​

var countSubstrings = function (s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        let s1 = '', s2 = '';
        for (let j = i; j < s.length; j++) {
            s1 += s[j], s2 = s[j] + s2;
            if (s1 === s2) count++;
        }
    }

    return count;
};

8、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

9、执行结果​

• 执行用时: 196 ms
• 内存消耗: 44.3 MB

这里的执行用时仍然比较高，是因为字符串拼接属于耗时操作。

10、解法3-中心扩展​

枚举所有可能的回文中心 s[i] 或 s[i]、s[i + 1]，若回文子串长度为奇数则其中心为 s[i]，回文子串长度为偶数则其中心为 s[i]、s[i + 1]；以中心向左右两边扩展，即左边界 l 减一右边界 r 加1，如果 s[l] 与 s[r] 相等则回文数加1。

11、代码​

var countSubstrings = function (s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let l = i, r = i; l >= 0 && s[l] === s[r]; l--, r++) count++;
        for (let l = i, r = i + 1; l >= 0 && s[l] === s[r]; l--, r++) count++;
    }
    return count;
};

12、复杂度​

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

13、执行结果​

1、题干​

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

2、解法1-暴力解法​

双指针 i 和 j 枚举所有子串的起点和终点，遍历 i 和 j 区间段内的字符判断其是否回文。

这种方式时间复杂度是 $O(n^3)$，复杂度太高，如果数据量再大点可能会超时。其中双指针枚举的时间复杂度是 $O(n^2)$，回文判断的时间复杂度是 $O(n)$。解法2就是在此基础上优化了回文判断的复杂度。

3、代码​

var countSubstrings = function (s) {
    function isPal(s, l, r) {
        for (let i = l; i < (l + r) / 2; i++) {
            if (s[i] !== s[l + r - i - 1]) return false;
        }
        return true
    }

    let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            if (isPal(s, i, j)) count++;
        }
    }

    return count;
};

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(1)$

5、执行结果​

• 执行用时: 308 ms
• 内存消耗: 38.4 MB

6、解法2-双指针​

该解法是解法1的优化版本。先使用双指针 i 和 j 枚举所有子串的起点和终点，同时分别按顺序和逆序累加所有遍历过的字符得到字符串 s1 和 s2，判断是否回文只需对 s1 和 s2 判等即可。这里将回文判断的时间复杂度从 $O(n)$ 优化到 $O(1)$，但整体空间复杂度从 $O(1)$ 升到 $O(n)$，算是空间换时间。

7、代码​

var countSubstrings = function (s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        let s1 = '', s2 = '';
        for (let j = i; j < s.length; j++) {
            s1 += s[j], s2 = s[j] + s2;
            if (s1 === s2) count++;
        }
    }

    return count;
};

8、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

9、执行结果​

• 执行用时: 196 ms
• 内存消耗: 44.3 MB

这里的执行用时仍然比较高，是因为字符串拼接属于耗时操作。

10、解法3-中心扩展​

枚举所有可能的回文中心 s[i] 或 s[i]、s[i + 1]，若回文子串长度为奇数则其中心为 s[i]，回文子串长度为偶数则其中心为 s[i]、s[i + 1]；以中心向左右两边扩展，即左边界 l 减一右边界 r 加1，如果 s[l] 与 s[r] 相等则回文数加1。

11、代码​

var countSubstrings = function (s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let l = i, r = i; l >= 0 && s[l] === s[r]; l--, r++) count++;
        for (let l = i, r = i + 1; l >= 0 && s[l] === s[r]; l--, r++) count++;
    }
    return count;
};

12、复杂度​

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

13、执行结果​

1、题干​

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

2、解法1-暴力解法​

双指针 i 和 j 枚举所有子串的起点和终点，遍历 i 和 j 区间段内的字符判断其是否回文。

这种方式时间复杂度是 $O(n^3)$，复杂度太高，如果数据量再大点可能会超时。其中双指针枚举的时间复杂度是 $O(n^2)$，回文判断的时间复杂度是 $O(n)$。解法2就是在此基础上优化了回文判断的复杂度。

3、代码​

var countSubstrings = function (s) {
    function isPal(s, l, r) {
        for (let i = l; i < (l + r) / 2; i++) {
            if (s[i] !== s[l + r - i - 1]) return false;
        }
        return true
    }

    let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            if (isPal(s, i, j)) count++;
        }
    }

    return count;
};

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(1)$

5、执行结果​

• 执行用时: 308 ms
• 内存消耗: 38.4 MB

6、解法2-双指针​

该解法是解法1的优化版本。先使用双指针 i 和 j 枚举所有子串的起点和终点，同时分别按顺序和逆序累加所有遍历过的字符得到字符串 s1 和 s2，判断是否回文只需对 s1 和 s2 判等即可。这里将回文判断的时间复杂度从 $O(n)$ 优化到 $O(1)$，但整体空间复杂度从 $O(1)$ 升到 $O(n)$，算是空间换时间。

7、代码​

var countSubstrings = function (s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        let s1 = '', s2 = '';
        for (let j = i; j < s.length; j++) {
            s1 += s[j], s2 = s[j] + s2;
            if (s1 === s2) count++;
        }
    }

    return count;
};

8、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

9、执行结果​

• 执行用时: 196 ms
• 内存消耗: 44.3 MB

这里的执行用时仍然比较高，是因为字符串拼接属于耗时操作。

10、解法3-中心扩展​

枚举所有可能的回文中心 s[i] 或 s[i]、s[i + 1]，若回文子串长度为奇数则其中心为 s[i]，回文子串长度为偶数则其中心为 s[i]、s[i + 1]；以中心向左右两边扩展，即左边界 l 减一右边界 r 加1，如果 s[l] 与 s[r] 相等则回文数加1。

11、代码​

var countSubstrings = function (s) {
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let l = i, r = i; l >= 0 && s[l] === s[r]; l--, r++) count++;
        for (let l = i, r = i + 1; l >= 0 && s[l] === s[r]; l--, r++) count++;
    }
    return count;
};

12、复杂度​

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

13、执行结果​

1、题干​

字符串 s 可以按下述步骤划分为若干长度为 k 的组：

• 第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
• 对于最后一组，如果字符串剩下的字符 不足 k 个，需使用字符 fill 来补全这一组字符。

注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。

给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。

示例 1：

输入：s = "abcdefghi", k = 3, fill = "x"
输出：["abc","def","ghi"]
解释：
前 3 个字符是 "abc" ，形成第一组。
接下来 3 个字符是 "def" ，形成第二组。
最后 3 个字符是 "ghi" ，形成第三组。
由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。
因此，形成 3 组，分别是 "abc"、"def" 和 "ghi" 。

示例 2：

输入：s = "abcdefghij", k = 3, fill = "x"
输出：["abc","def","ghi","jxx"]
解释：
与前一个例子类似，形成前三组 "abc"、"def" 和 "ghi" 。
对于最后一组，字符串中仅剩下字符 'j' 可以用。为了补全这一组，使用填充字符 'x' 两次。
因此，形成 4 组，分别是 "abc"、"def"、"ghi" 和 "jxx" 。

提示：

• 1 <= s.length <= 100
• s 仅由小写英文字母组成
• 1 <= k <= 100
• fill 是一个小写英文字母

2、解题思路​

遍历字符串 s 中的字符，每 k 个组成一个新字符串并推入结果数组，最末尾的子串若长度不足 k 则补充字符 fill

3、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

4、代码​

var divideString = function (s, k, fill) {
    const res = [];
    for (let i = 0; i < s.length; i += k) {
        const str = s.slice(i, i + k);
        res.push(str.length === k ? str : str.padEnd(k, fill))
    }
    return res;
};

5、执行结果​

• 执行用时： 64 ms , 在所有 JavaScript 提交中击败了 94.57% 的用户
• 内存消耗： 39.1 MB , 在所有 JavaScript 提交中击败了 59.78% 的用户

1、题干​

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1：

输入："112358"
输出：true 
解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2：

输入："199100199"
输出：true 
解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

提示：

• 1 <= num.length <= 35
• num 仅由数字（0 - 9）组成

进阶：你计划如何处理由过大的整数输入导致的溢出?

2、解法1-回溯​

总体思路：使用回溯对所有可能性进行匹配直到成功。大体步骤如下：

• 使用递归实现回溯算法，递归函数match，参数l、m、r分别表示待匹配的3个数的起始位置
• match函数第一步先处理边界情况、0开头的特殊情况
• 第二步从num字符串中取出前两个数并求和，得到第三个数n3
• 第三步剪枝，如果剩余字符比要查找的结果更短，直接返回false
• 第四步在剩余字符串中查找n3是否存在，若存在且正好用尽所有字符则返回true
• 若不存在则尝试r右移一位以及m右移一位的情况
  

注意点

• 测试用例中不存在大整数，因此没有做大整数特殊处理
• 边界条件、特殊情况略多，如果不能AC可以多调试看看是否边界没处理好
• 一定要剪枝，否则大概率会超时

3、代码​

var isAdditiveNumber = function (num) {
    function match(l, m, r) {
        // 处理边界情况、特殊情况（0开头的数）
        if (r > num.length || m > num.length - 1 || (num[l] === '0' && m - l > 1)) return false;
        if (m >= r) return match(l, m, r + 1);
        if (num[m] === '0' && r - m > 1) return match(l, m + 1, r);

        const n3 = `${+num.slice(l, m) + +num.slice(m, r)}`;
        // 剪枝：如果剩余字符比要查找的结果更短，直接返回false
        if (n3.length > num.length - r) return false;
        // 匹配成功 🚀🚀🚀
        if (num.slice(r, r + n3.length) === n3 && (r + n3.length === num.length || match(m, r, r + n3.length))) return true;

        // 匹配失败：尝试查找其他可能性
        return match(l, m, r + 1) || match(l, m + 1, r);
    }
    return match(0, 1, 2);
};

4、执行结果​

执行用时: 108 ms 内存消耗: 44.7 MB

5、解法1-优化版​

• 问题1：确定开头两个数字之后（num.slice(r, r + n3.length) === n3）的后续匹配方式存在无效遍历，原先使用递归进行后续匹配，每次右移1位，因此存在大量无效匹配。
• 问题2：已遍历过的情况没有直接跳过，导致存在大量重复遍历。
• 优化1：确定开头两个数字之后，由于后面的数字是前面累加而来，因此后面的数字都是确定的，可以直接使用while循环匹配累加和。
• 优化2：使用哈希表记录已遍历过的情况，后续直接跳过这些情况，进行记忆化搜索。（感谢评论区 @Jvaeyhcd 的提醒）

在用例"1991000199299498797"中遍历次数从解法1的15000+次降到99次。

6、代码​

var isAdditiveNumber = function (num) {
    const set = new Set();

    function match(l, m, r) {
        if (set.has(`${l}-${m}-${r}`)) return false;
        set.add(`${l}-${m}-${r}`);
        if (r > num.length || m > num.length - 1 || (num[l] === '0' && m - l > 1)) return false;
        if (r - m > num.length - r || m - l > num.length - r) return false;

        if (m >= r) return match(l, m, r + 1);
        if (num[m] === '0' && r - m > 1) return match(l, m + 1, r);

        let r2 = r, n1 = +num.slice(l, m), n2 = +num.slice(m, r), n3 = n1 + n2;
        while (num.slice(r2, r2 + `${n3}`.length) === `${n3}`) {
            (r2 = r2 + `${n3}`.length), (n1 = n2), (n2 = n3), (n3 = n1 + n2);
        }
        if (r2 === num.length) return true;

        return match(l, m, r + 1) || match(l, m + 1, r);
    }
    return match(0, 1, 2);
};

7、执行结果​

执行用时: 68 ms 内存消耗: 38.1 MB

8、解法2-双指针遍历​

总体思路：双层遍历确定开头两个数字之后，由于后面的数字是前面累加而来，因此后面的数字都是确定的，可以直接使用while循环匹配累加和。

在用例"1991000199299498797"中遍历次数从解法1的15000+次降到120次。

9、代码​

var isAdditiveNumber = function (num) {
    for (let m = 1; m < num.length; m++) {
        let n1 = +num.slice(0, m);
        if (num[0] === '0' && m > 1) return false;

        for (let r = m + 1; r < num.length; r++) {
            if (num[m] === '0' && r - m > 1) break;
            let n2 = +num.slice(m, r), r_2 = r, n_1 = n1, n3 = n1 + n2;
            while (num.slice(r_2, r_2 + `${n3}`.length) === `${n3}`) {
                (r_2 = r_2 + `${n3}`.length), (n_1 = n2), (n2 = n3), (n3 = n_1 + n2);
            }
            if (r_2 === num.length) return true;
        }
    }

    return false;
};

10、执行结果​

执行用时: 60 ms 内存消耗: 38.1 MB

1、题干​

LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。

给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下，接下来每个键都 恰好 在前一个键松开时被按下。

测试人员想要找出按键 持续时间最长 的键。第 i 次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。

注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。

请返回单次按键 持续时间最长 的键，如果有多个这样的键，则返回 按字母顺序排列最大 的那个键。

示例 1：

输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd"
输出："c"
解释：按键顺序和持续时间如下：
按下 'c' ，持续时间 9（时间 0 按下，时间 9 松开）
按下 'b' ，持续时间 29 - 9 = 20（松开上一个键的时间 9 按下，时间 29 松开）
按下 'c' ，持续时间 49 - 29 = 20（松开上一个键的时间 29 按下，时间 49 松开）
按下 'd' ，持续时间 50 - 49 = 1（松开上一个键的时间 49 按下，时间 50 松开）
按键持续时间最长的键是 'b' 和 'c'（第二次按下时），持续时间都是 20
'c' 按字母顺序排列比 'b' 大，所以答案是 'c'

示例 2：

输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
输出："a"
解释：按键顺序和持续时间如下：
按下 's' ，持续时间 12
按下 'p' ，持续时间 23 - 12 = 11
按下 'u' ，持续时间 36 - 23 = 13
按下 'd' ，持续时间 46 - 36 = 10
按下 'a' ，持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ，持续时间 16

提示：

• releaseTimes.length == n
• keysPressed.length == n
• 2 <= n <= 1000
• 1 <= releaseTimes[i] <= 109
• releaseTimes[i] < releaseTimes[i+1]
• keysPressed 仅由小写英文字母组成

2、解题思路​

根据题意遍历所有按键keysPressed，若按键时长releaseTimes[i] - (releaseTimes[i - 1] || 0)超过以往最大时长maxTime或等于以往最大时长且该按键字典序更大，则将该时长记为最大时长maxTime，该按键记为持续时间最长的键key，最终返回key即可。

3、代码​

var slowestKey = function (releaseTimes, keysPressed) {
    let maxTime = 0, key = keysPressed[0];
    for (let i = 0; i < keysPressed.length; i++) {
        const time = releaseTimes[i] - (releaseTimes[i - 1] || 0);
        if (time > maxTime || (time === maxTime && keysPressed[i] > key)) maxTime = time, key = keysPressed[i];
    }
    return key;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5、执行结果​