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

1、题干​

给你一个下标从 0 开始长度为 n 的字符串 num ，它只包含数字。

如果对于 每个 0 <= i < n 的下标 i ，都满足数位 i 在 num 中出现了 num[i]次，那么请你返回 true ，否则返回 false 。

示例 1：

输入：num = "1210"
输出：true
解释：
num[0] = '1' 。数字 0 在 num 中出现了一次。
num[1] = '2' 。数字 1 在 num 中出现了两次。
num[2] = '1' 。数字 2 在 num 中出现了一次。
num[3] = '0' 。数字 3 在 num 中出现了零次。
"1210" 满足题目要求条件，所以返回 true 。

示例 2：

输入：num = "030"
输出：false
解释：
num[0] = '0' 。数字 0 应该出现 0 次，但是在 num 中出现了两次。
num[1] = '3' 。数字 1 应该出现 3 次，但是在 num 中出现了零次。
num[2] = '0' 。数字 2 在 num 中出现了 0 次。
下标 0 和 1 都违反了题目要求，所以返回 false 。

提示：

• n == num.length
• 1 <= n <= 10
• num 只包含数字。

2、思路​

模拟

3、代码​

function digitCount(num: string): boolean {
    for (let i = 0; i < 10; i++) {
        let c = +num[i] || 0;
        for (const n of num) {
            if (+n === i) c--;
        }
        if (c) return false;
    }

    return true;
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个字符串数组 words 和一个字符串 pref 。

返回 words 中以 pref 作为 前缀 的字符串的数目。

字符串 s 的 前缀 就是  s 的任一前导连续字符串。

示例 1：

输入：words = ["pay","attention","practice","attend"], pref = "at"
输出：2
解释：以 "at" 作为前缀的字符串有两个，分别是："attention" 和 "attend" 。

示例 2：

输入：words = ["leetcode","win","loops","success"], pref = "code"
输出：0
解释：不存在以 "code" 作为前缀的字符串。

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length, pref.length <= 100
• words[i] 和 pref 由小写英文字母组成

2、思路​

根据题意模拟

3、代码​

function prefixCount(words: string[], pref: string): number {
    return words.reduce((a, c) => a + +c.startsWith(pref), 0);
};

4、复杂度​

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

5、执行结果​

1、题干​

句子是由若干 token 组成的一个列表，token 间用 单个 空格分隔，句子没有前导或尾随空格。每个 token 要么是一个由数字 0-9 组成的不含前导零的 正整数 ，要么是一个由小写英文字母组成的 单词 。

• 示例，"a puppy has 2 eyes 4 legs" 是一个由 7 个 token 组成的句子："2" 和 "4" 是数字，其他像 "puppy" 这样的 tokens 属于单词。

给你一个表示句子的字符串 s ，你需要检查 s 中的 全部 数字是否从左到右严格递增（即，除了最后一个数字，s 中的 每个 数字都严格小于它 右侧 的数字）。

如果满足题目要求，返回 true ，否则，返回 false 。

示例 1：

输入：s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
输出：true
解释：句子中的数字是：1, 3, 4, 6, 12 。
这些数字是按从左到右严格递增的 1 < 3 < 4 < 6 < 12 。

示例 2：

输入：s = "hello world 5 x 5"
输出：false
解释：句子中的数字是：5, 5 。这些数字不是严格递增的。

示例 3：

输入：s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
输出：false
解释：s 中的数字是：7, 51, 50, 60 。这些数字不是严格递增的。

示例 4：

输入：s = "4 5 11 26"
输出：true
解释：s 中的数字是：4, 5, 11, 26 。
这些数字是按从左到右严格递增的：4 < 5 < 11 < 26 。

提示：

• 3 <= s.length <= 200
• s 由小写英文字母、空格和数字 0 到 9 组成（包含 0 和 9）
• s 中数字 token 的数目在 2 和 100 之间（包含 2 和 100）
• s 中的 token 之间由单个空格分隔
• s 中至少有 两个 数字
• s 中的每个数字都是一个 小于 100 的 正 数，且不含前导零
• s 不含前导或尾随空格

2、思路​

正则提取所有数字，再遍历所有数字是否单调递增

3、代码​

function areNumbersAscending(s: string): boolean {
    return s.split(/[^\d]+/).filter(Boolean).every((n, i, nums) => +n > (+nums[i - 1] || -1));
};

function areNumbersAscending(s: string): boolean {
    const nums = s.match(/\d+/g);
    return nums.every((n, i) => +n > (+nums[i - 1] || -1));
};

4、执行结果​

1、题干​

给你一个由小写英文字母组成的字符串 s ，请你找出并返回第一个出现 两次 的字母。

注意：

• 如果 a 的 第二次 出现比 b 的 第二次 出现在字符串中的位置更靠前，则认为字母 a 在字母 b 之前出现两次。
• s 包含至少一个出现两次的字母。

示例 1：

输入：s = "abccbaacz"
输出："c"
解释：
字母 'a' 在下标 0 、5 和 6 处出现。
字母 'b' 在下标 1 和 4 处出现。
字母 'c' 在下标 2 、3 和 7 处出现。
字母 'z' 在下标 8 处出现。
字母 'c' 是第一个出现两次的字母，因为在所有字母中，'c' 第二次出现的下标是最小的。

示例 2：

输入：s = "abcdd"
输出："d"
解释：
只有字母 'd' 出现两次，所以返回 'd' 。

提示：

• 2 <= s.length <= 100
• s 由小写英文字母组成
• s 包含至少一个重复字母

2、思路​

记录字符出现次数，首次重复出现则返回

3、代码​

function repeatedCharacter(s: string): string {
    const dict = {};
    for (const c of s) {
        if (dict[c]) return c;
        dict[c] = 1;
    }
};

4、复杂度​

• 时间复杂度：$O(C)$，其中 $C<=26$
• 空间复杂度：$O(C)$，其中 $C<=26$

1、题干​

给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：

1. 选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。
2. 选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。
3. 前缀和后缀在字符串中任意位置都不能有交集。
4. 前缀和后缀包含的所有字符都要相同。
5. 同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

示例 1：

输入：s = "ca"
输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。

示例 2：

输入：s = "cabaabac"
输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "" 。

示例 3：

输入：s = "aabccabba"
输出：3
解释：最优操作序列为：
- 选择前缀 "aa" 和后缀 "a" 并删除它们，得到 s = "bccabb" 。
- 选择前缀 "b" 和后缀 "bb" 并删除它们，得到 s = "cca" 。

提示：

• 1 <= s.length <= 105
• s 只包含字符 'a'，'b' 和 'c' 。

2、思路1​

双指针遍历直到指针交叉或对应不同字符

3、代码​

function minimumLength(s: string): number {
    let l = 0, r = s.length - 1;
    while (l < r && s[l] === s[r]) {
        const c = s[l];
        while (l <= r && s[l] === c) l++;
        while (l <= r && s[r] === c) r--;
    }
    return r - l + 1;
};

4、复杂度​

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

5、执行结果​

6、思路2​

按题意模拟，剔除首尾相同字符，直到首尾字符不同或字符串长度小于2

7、代码​

function minimumLength(s: string): number {
    while (s[1] && s[0] === s[s.length - 1]) {
        const c = s[0];
        while (s[0] === c) s = s.slice(1);
        while (s[s.length - 1] === c) s = s.slice(0, s.length - 1);
    }
    return s.length;
};

8、执行结果​

9、思路3​

按题意模拟，借助正则剔除首尾相同字符，直到首尾字符不同或字符串长度小于2

10、代码​

function minimumLength(s: string): number {
    if (!s[1] || s[0] !== s[s.length - 1]) return s.length;
    return minimumLength(s.replace(new RegExp(`^${s[0]}+|${s[0]}+$`, 'g'), ''));
};

11、执行结果​

1、题干​

给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。

同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。

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

示例 1：

输入：s = "abbcccaa"
输出：13
解释：同构子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：

输入：s = "xy"
输出：2
解释：同构子字符串是 "x" 和 "y" 。

示例 3：

输入：s = "zzzzz"
输出：15

提示：

• 1 <= s.length <= 105
• s 由小写字符串组成

2、思路​

先提取连续且重复的字母组成的单词，再累计每个单词长度的等差数列和

3、代码​

function countHomogenous(s: string): number {
    return s.match(/([a-z])\1*/g).reduce((a, c) => (a + c.length * (c.length + 1) / 2) % (1e9 + 7), 0);
};

4、执行结果​

1、题干​

给你一个字符串 s ，返回 s 中 同质子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。

同质字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。

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

示例 1：

输入：s = "abbcccaa"
输出：13
解释：同质子字符串如下所列：
"a"   出现 3 次。
"aa"  出现 1 次。
"b"   出现 2 次。
"bb"  出现 1 次。
"c"   出现 3 次。
"cc"  出现 2 次。
"ccc" 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：

输入：s = "xy"
输出：2
解释：同质子字符串是 "x" 和 "y" 。

示例 3：

输入：s = "zzzzz"
输出：15

提示：

• 1 <= s.length <= 105
• s 由小写字符串组成。

2、思路​

先提取连续且重复的字母组成的单词，再累计每个单词长度的等差数列和

3、代码​

function countHomogenous(s: string): number {
    return s.match(/([a-z])\1*/g).reduce((a, c) => (a + c.length * (c.length + 1) / 2) % (1e9 + 7), 0);
};

4、执行结果​

1、题干​

一个字符串的 美丽值 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

• 比方说，"abaacc" 的美丽值为 3 - 1 = 2 。

给你一个字符串 s ，请你返回它所有子字符串的 美丽值 之和。

示例 1：

输入：s = "aabcb"
输出：5
解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：

输入：s = "aabcbaa"
输出：17

提示：

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

Problem: 1781. 所有子字符串美丽值之和

2、思路​

枚举所有子串，累计所有美丽值

没想到官解也是暴力枚举，甚至没有优化

3、Code​

function beautySum(s: string): number {
    let ans = 0, chars = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        chars[s.charCodeAt(i) - 97] += 1;

        const counts = [...chars];
        for (let j = 0; j < i - 1; j++) {
            let max = 1, min = s.length;
            for (const c of counts) {
                if (c > max) max = c;
                if (c && c < min) min = c;
            }
            ans += max - min;
            counts[s.charCodeAt(j) - 97] -= 1;
        }
    }

    return ans;
}

4、复杂度​

• 时间复杂度：$O(C*n^2)$，$C=26$
• 空间复杂度：$O(C)$

5、执行结果​

1、题干​

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

示例 1：

输入：boxes = "110"
输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入：boxes = "001011"
输出：[11,8,5,4,3,4]

提示：

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] 为 '0' 或 '1'

Problem: 1769. 移动所有球到每个盒子所需的最小操作数

2、思路1​

双层循环暴力枚举

3、Code​

function minOperations(boxes: string): number[] {
    const ans = new Array(boxes.length).fill(0);
    for (let i = 0; i < ans.length; i++) {
        for (let j = 0; j < boxes.length; j++) {
            if (boxes[j] === '1') ans[i] += Math.abs(i - j);
        }
    }
    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

单层循环累加左右步数

关键点：左半边有 lc 个 1 时，每移动一次左半边步数 ls 需累加 lc，同理右半边步数 rs 需减去 rc

7、Code​

function minOperations(boxes: string): number[] {
    let rc = 0, rs = 0, lc = 0, ls = 0;
    const ans = new Array(boxes.length).fill(0);

    for (let i = 0; i < boxes.length; i++) {
        if (boxes[i] === '1') rc += 1, rs += i;
    }

    for (let i = 0; i < ans.length; i++) {
        ans[i] = ls + rs;
        if (boxes[i] === '1') rc--, lc++;
        rs -= rc, ls += lc;
    }
    
    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 s = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = s。

输入一组查询单词，输出其中可扩张的单词数量。

示例：

输入： 
s = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。

提示：

• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s 和所有在 words 中的单词都只由小写字母组成。

Problem: 809. 情感丰富的文字

2、思路​

总体思路是：先提取字符串 s 的 pattern，然后遍历 words 中每一项是否与 pattern 相匹配。这里使用正则实现。

• 提取字符串 s 的正则
  • 将 s 中连续 3 个以上相同的字符 a 替换为 a{1,a.count}，比如 ooooo 替换为 o{1,5}
  • 替换后的字符串添加首尾标志 ^、$ 并转为正则
• 遍历 words 并与正则匹配，若匹配则结果累计 1

3、Code​

function expressiveWords(s: string, words: string[]): number {
    const r = s.replace(/(\w)\1{2,}/g, (m, a) => `${a}{1,${m.length}}`);
    const reg = new RegExp(`^${r}$`);
    return words.reduce((a, c) => a + +reg.test(c), 0);
};

4、执行结果​