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

1、题干​

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。

如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。

文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。

• 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符串和 "/" 不是。

示例 1：

输入：folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
输出：["/a","/c/d","/c/f"]
解释："/a/b" 是 "/a" 的子文件夹，而 "/c/d/e" 是 "/c/d" 的子文件夹。

示例 2：

输入：folder = ["/a","/a/b/c","/a/b/d"]
输出：["/a"]
解释：文件夹 "/a/b/c" 和 "/a/b/d" 都会被删除，因为它们都是 "/a" 的子文件夹。

示例 3：

输入: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
输出: ["/a/b/c","/a/b/ca","/a/b/d"]

提示：

• 1 <= folder.length <= 4 * 104
• 2 <= folder[i].length <= 100
• folder[i] 只包含小写字母和 '/'
• folder[i] 总是以字符 '/' 起始
• folder 每个元素都是 唯一 的

2、思路1-排序​

• 对文件夹数组 folder 升序排序，初始化父文件夹 pf = folder[0] + '/'
• 遍历检查所有文件夹 folder[i] 与当前父文件夹 pf 是否父子关系，是则说明 folder[i] 是子文件夹，不是则将 folder[i] 置为父文件夹继续检查

3、代码​

function removeSubfolders(folder: string[]): string[] {
    folder.sort();

    const ans = [folder[0]];
    let pf = folder[0] + '/';

    for (let i = 1; i < folder.length; i++) {
        if (!folder[i].startsWith(pf)) {
            ans.push(folder[i]);
            pf = folder[i] + '/';
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(nm*logn)$
• 空间复杂度：$O(logn)$

5、执行结果​

6、思路2-哈希​

将 folder 数组中所有文件夹存入哈希集合 set，遍历检查文件夹 folder[i] 所有前缀路径，若前缀路径存在于 set 中，则说明 folder[i] 是子文件夹

7、代码​

function removeSubfolders(folder: string[]): string[] {
    const ans = [], set = new Set(folder);

    for (const f of folder) {
        let found = false;

        for (let i = 0; i < f.length;) {
            i = f.indexOf('/', i + 1);
            if (i < 0) break;

            const dir = f.slice(0, i);

            if (set.has(dir)) {
                found = true;
                break;
            }
        }

        if (!found) ans.push(f);
    }

    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

力扣公司的员工都使用员工卡来开办公室的门。每当一个员工使用一次他的员工卡，安保系统会记录下员工的名字和使用时间。如果一个员工在一小时时间内使用员工卡的次数大于等于三次，这个系统会自动发布一个 警告 。

给你字符串数组 keyName 和 keyTime ，其中 [keyName[i], keyTime[i]] 对应一个人的名字和他在 某一天 内使用员工卡的时间。

使用时间的格式是 24小时制 ，形如 "HH:MM" ，比方说 "23:51" 和 "09:49" 。

请你返回去重后的收到系统警告的员工名字，将它们按 字典序升序 排序后返回。

请注意 "10:00" - "11:00" 视为一个小时时间范围内，而 "22:51" - "23:52" 不被视为一小时时间范围内。

示例 1：

输入：keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
输出：["daniel"]
解释："daniel" 在一小时内使用了 3 次员工卡（"10:00"，"10:40"，"11:00"）。

示例 2：

输入：keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
输出：["bob"]
解释："bob" 在一小时内使用了 3 次员工卡（"21:00"，"21:20"，"21:30"）。

提示：

• 1 <= keyName.length, keyTime.length <= 105
• keyName.length == keyTime.length
• keyTime 格式为 "HH:MM" 。
• 保证 [keyName[i], keyTime[i]] 形成的二元对 互不相同 。
• 1 <= keyName[i].length <= 10
• keyName[i] 只包含小写英文字母。

2、思路1​

哈希表存储员工姓名（键）和开门时间数组（值），时间转为分钟数并排序，最后检查每个员工的开门时间是否违规

3、代码​

function alertNames(names: string[], times: string[]): string[] {
    const map = new Map<string, number[]>();
    for (let i = 0; i < names.length; i++) {
        if (!map.has(names[i])) map.set(names[i], []);
        map.get(names[i]).push(60 * (+times[i].slice(0, 2)) + +(times[i].slice(3)));
    }

    const ans = [];
    for (const [name, minutes] of map) {
        if (minutes.length < 3) continue;

        minutes.sort((a, b) => a - b);
        for (let i = 0; i < minutes.length - 2 && ans.at(-1) !== name; i++) {
            if (minutes[i + 2] - minutes[i] <= 60) ans.push(name);
        }
    }

    return ans.sort();
};

4、复杂度​

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

5、执行结果​

6、思路2​

二维数组存储员工姓名和开门时间，时间转为分钟数，对二维数组按姓名和分钟数升序排序，最后检查每个员工的开门时间是否违规

7、代码​

function alertNames(names: string[], times: string[]): string[] {
    const matrix: [string, number][] = names.map((n, i) => [n, 60 * (+times[i].slice(0, 2)) + +(times[i].slice(3))]);
    matrix.sort((a, b) => {
        if (a[0] === b[0]) return a[1] - b[1];
        return a[0] > b[0] ? 1 : -1;
    });

    const ans = [];

    for (let i = 0; i < matrix.length - 2; i++) {
        if (matrix[i + 2][0] !== matrix[i][0] || matrix[i][0] === ans.at(-1)) continue;
        if (matrix[i + 2][1] - matrix[i][1] <= 60) ans.push(matrix[i][0]);
    }

    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

给你字符串 key 和 message ，分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下：

1. 使用 key 中 26 个英文小写字母第一次出现的顺序作为替换表中的字母 顺序 。
2. 将替换表与普通英文字母表对齐，形成对照表。
3. 按照对照表 替换 message 中的每个字母。
4. 空格 ' ' 保持不变。

• 例如，key = "happy boy"（实际的加密密钥会包含字母表中每个字母 至少一次），据此，可以得到部分对照表（'h' -> 'a'、'a' -> 'b'、'p' -> 'c'、'y' -> 'd'、'b' -> 'e'、'o' -> 'f'）。

返回解密后的消息。

示例 1：

输入：key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
输出："this is a secret"
解释：对照表如上图所示。
提取 "the quick brown fox jumps over the lazy dog" 中每个字母的首次出现可以得到替换表。

示例 2：

输入：key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
输出："the five boxing wizards jump quickly"
解释：对照表如上图所示。
提取 "eljuxhpwnyrdgtqkviszcfmabo" 中每个字母的首次出现可以得到替换表。

提示：

• 26 <= key.length <= 2000
• key 由小写英文字母及 ' ' 组成
• key 包含英文字母表中每个字符（'a' 到 'z'）至少一次
• 1 <= message.length <= 2000
• message 由小写英文字母和 ' ' 组成

2、思路​

借助哈希集合做字母关系映射

3、代码​

function decodeMessage(key: string, message: string): string {
    const B = ' ', chars = [...new Set(key)].filter(c => c !== B);
    return [].map.call(message, (c) => c === B ? B : String.fromCharCode(97 + chars.indexOf(c))).join('');
};

4、复杂度​

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

5、执行结果​

1、题干​

给你一个字符串 s ，每 两个 连续竖线 '|' 为 一对 。换言之，第一个和第二个 '|' 为一对，第三个和第四个 '|' 为一对，以此类推。

请你返回 不在 竖线对之间，s 中 '*' 的数目。

注意，每个竖线 '|' 都会 恰好 属于一个对。

示例 1：

输入：s = "l|*e*et|c**o|*de|"
输出：2
解释：不在竖线对之间的字符加粗加斜体后，得到字符串："l|*e*et|c**o|*de|" 。
第一和第二条竖线 '|' 之间的字符不计入答案。
同时，第三条和第四条竖线 '|' 之间的字符也不计入答案。
不在竖线对之间总共有 2 个星号，所以我们返回 2 。

示例 2：

输入：s = "iamprogrammer"
输出：0
解释：在这个例子中，s 中没有星号。所以返回 0 。

示例 3：

输入：s = "yo|uar|e**|b|e***au|tifu|l"
输出：5
解释：需要考虑的字符加粗加斜体后："yo|uar|e**|b|e***au|tifu|l" 。不在竖线对之间总共有 5 个星号。所以我们返回 5 。

提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母，竖线 '|' 和星号 '*' 。
• s 包含 偶数 个竖线 '|' 。

2、思路1​

模拟，设置标志位用于判断星号是否处于竖线对区间内

3、代码​

function countAsterisks(s: string): number {
    let ans = 0, start = false;

    for (const c of s) {
        if (c === '|') start = !start;
        else if (!start && c === '*') ans++;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

正则，剔除竖线对及其区间内字符后统计星号数量

7、代码​

function countAsterisks(s: string): number {
    return s.replace(/\|[^|]*\|/g, '').match(/\*/g)?.length || 0;
};

8、执行结果​

1、题干​

给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。

最好 英文字母的大写和小写形式必须 都 在 s 中出现。

英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。

示例 1：

输入：s = "lEeTcOdE"
输出："E"
解释：
字母 'E' 是唯一一个大写和小写形式都出现的字母。

示例 2：

输入：s = "arRAzFif"
输出："R"
解释：
字母 'R' 是大写和小写形式都出现的最好英文字母。
注意 'A' 和 'F' 的大写和小写形式也都出现了，但是 'R' 比 'F' 和 'A' 更好。

示例 3：

输入：s = "AbCdEfGhIjK"
输出：""
解释：
不存在大写和小写形式都出现的字母。

提示：

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

2、思路1​

哈希表模拟

3、代码​

function greatestLetter(s: string): string {
    const dict = new Set();
    let ans = '';

    for (const c of s) {
        dict.add(c);
        const l = c.toLowerCase(), L = c.toUpperCase();
        if (L > ans && dict.has(l) && dict.has(L)) ans = L;
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

倒序枚举字母表

7、代码​

function greatestLetter(s: string): string {
    for (let i = 90; i >= 65; i--) {
        const C = String.fromCharCode(i), c = C.toLowerCase();
        if (s.includes(C) && s.includes(c)) return C;
    }

    return '';
};

8、复杂度​

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

9、执行结果​

1、题干​

小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

• x 是 y 的一个前缀；
• 如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

示例 1：

输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

示例 2：

输入：n = 5, k = 73
输出："aaszz"

提示：

• 1 <= n <= 105
• n <= k <= 26 * n

2、思路1​

数组+贪心模拟，使用长度为 n 的数组 codes 存储每个字符的 数值，数组 codes 之和代表 字符串的数值，初始化时 codes 所有元素都置为 1（代表字符 a），之后从数组尾部开始将元素替换成尽可能大的 数值 直至 k 为 0

3、代码​

function getSmallestString(n: number, k: number): string {
    k = k - n;
    const codes = new Array(n).fill(1);

    for (let i = codes.length - 1; i > -1 && k > 0; i--) {
        codes[i] = Math.min(k + 1, 26);
        k = k - codes[i] + 1;
    }

    return codes.map(c => String.fromCharCode(96 + c)).join('');
};

4、复杂度​

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

5、执行结果​

虽然时间复杂度和空间复杂度已经很不错，但是由于数组存储数据，以及字符串操作过多导致消耗的时间和内存偏高。下面对此稍加优化。

6、思路2​

从上述模拟过程可以推断出，所求最小字符串的形式是 aaaaamzzzzz，即 若干个 a + 一个中间字符 + 若干个 z。因此只要求出 a 的个数、z 的个数、以及中间字符，就能拼接出所求最小字符串。

7、代码​

function getSmallestString(n: number, k: number): string {
    let na = 0, nz = 0;
    for (k -= n; k >= 25; k -= 25)  nz++;
    na = n - nz - (k > 0 ? 1 : 0);

    const m = k > 0 ? String.fromCharCode(97 + k) : '';

    return 'a'.repeat(na) + m + 'z'.repeat(nz);
};

8、复杂度​

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

9、执行结果​

1、题干​

如果一个密码满足以下所有条件，我们称它是一个 强 密码：

• 它有至少 8 个字符。
• 至少包含 一个小写英文 字母。
• 至少包含 一个大写英文 字母。
• 至少包含 一个数字 。
• 至少包含 一个特殊字符 。特殊字符为："!@#$%^&*()-+" 中的一个。
• 它 不 包含 2 个连续相同的字符（比方说 "aab" 不符合该条件，但是 "aba" 符合该条件）。

给你一个字符串 password ，如果它是一个 强 密码，返回 true，否则返回 false 。

示例 1：

输入：password = "IloveLe3tcode!"
输出：true
解释：密码满足所有的要求，所以我们返回 true 。

示例 2：

输入：password = "Me+You--IsMyDream"
输出：false
解释：密码不包含数字，且包含 2 个连续相同的字符。所以我们返回 false 。

示例 3：

输入：password = "1aB!"
输出：false
解释：密码不符合长度要求。所以我们返回 false 。

提示：

• 1 <= password.length <= 100
• password 包含字母，数字和 "!@#$%^&*()-+" 这些特殊字符。

2、思路1​

简单的多个正则匹配，一个正则对应一个条件

3、代码​

function strongPasswordCheckerII(password: string): boolean {
    return !/(.)\1/.test(password) && [/.{8}/, /[a-z]/, /[A-Z]/, /\d/, /[!@#$%^&*()+-]/].every(r => r.test(password));
};

4、执行结果​

5、思路2​

复杂的单个正则匹配，再次把看了又忘忘了又看的 前瞻后顾 预习了一遍 🤡

• 至少 8 个字符：/^.{8,}$/

• 至少包含一个小写字母：使用前瞻断言，限定整串字符的 pattern 是 .*[a-z]，具体正则为 /^(?=.*[a-z]).{8,}$/

• 至少包含一个小写字母、一个大写字母：使用两个前瞻断言，限定整串字符的 pattern 必须同时满足 .*[a-z] 与 .*[A-Z]，具体正则为 /^(?=.*[a-z])(?=.*[A-Z]).{8,}$，其他条件同理

• 不包含 2 个连续相同的字符：使用否定前瞻断言，限定整串字符的 pattern 不能是 .*(.)\1，具体正则为 /^(?!.*(.)\1).{8,}$/

• 完整正则为：/^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[!@#$%^&*()+-])(?!.*(.)\1).{8,}$/

• 也能这样写：/^(?=.{8,})(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[!@#$%^&*()+-])(?!.*(.)\1).+$/，一个前瞻断言对应一个条件

6、代码​

function strongPasswordCheckerII(password: string): boolean {
    return /^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[!@#$%^&*()+-])(?!.*(.)\1).{8,}$/.test(password);
};

7、执行结果​

1、题干​

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。比方说，"Hello World" ，"HELLO" ，"hello world hello world" 都是句子。每个单词都 只 包含大写和小写英文字母。

如果两个句子 sentence1 和 sentence2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。比方说，sentence1 = "Hello my name is Jane" 且 sentence2 = "Hello Jane" ，我们可以往 sentence2 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 sentence1 。

给你两个句子 sentence1 和 sentence2 ，如果 sentence1 和 sentence2 是相似的，请你返回 true ，否则返回 false 。

示例 1：

输入：sentence1 = "My name is Haley", sentence2 = "My Haley"
输出：true
解释：可以往 sentence2 中 "My" 和 "Haley" 之间插入 "name is" ，得到 sentence1 。

示例 2：

输入：sentence1 = "of", sentence2 = "A lot of words"
输出：false
解释：没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。

示例 3：

输入：sentence1 = "Eating right now", sentence2 = "Eating"
输出：true
解释：可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。

示例 4：

输入：sentence1 = "Luky", sentence2 = "Lucccky"
输出：false

提示：

• 1 <= sentence1.length, sentence2.length <= 100
• sentence1 和 sentence2 都只包含大小写英文字母和空格。
• sentence1 和 sentence2 中的单词都只由单个空格隔开。

2、思路1​

双指针模拟，对比首尾单词是否匹配直至指针相遇

3、代码​

function areSentencesSimilar(s1: string, s2: string): boolean {
    const words1 = s1.split(' '), words2 = s2.split(' ');
    const ml = Math.min(words1.length, words2.length);

    let i = 0, j = 0;
    while (i < ml && j < ml) {
        if (words1[i] === words2[i]) i++;
        else if (i < ml - j && words1.at(-j - 1) === words2.at(-j - 1)) j++;
        else break;
    }

    return i + j === ml;
};

4、复杂度​

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

5、执行结果​

6、思路2​

双端队列模拟，移除首尾相同单词直至某个队列为空。

• 没有自带的双端队列，这里使用数组代替，出队时间复杂度会更高
• 队列的实现比双指针更简单，不用考虑那么多边界问题，下次不折腾了

7、代码​

function areSentencesSimilar(s1: string, s2: string): boolean {
    const words1 = s1.split(' '), words2 = s2.split(' ');

    while (words1.length && words2.length) {
        if (words1.at(-1) === words2.at(-1)) words1.pop(), words2.pop();
        else if (words1[0] === words2[0]) words1.shift(), words2.shift();
        else break;
    }

    return !words1.length || !words2.length;
};

8、复杂度​

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

9、执行结果​

1、题干​

给你两个下标从 0 开始的字符串 s 和 target 。你可以从 s 取出一些字符并将其重排，得到若干新的字符串。

从 s 中取出字符并重新排列，返回可以形成 target 的 最大 副本数。

示例 1：

输入：s = "ilovecodingonleetcode", target = "code"
输出：2
解释：
对于 "code" 的第 1 个副本，选取下标为 4 、5 、6 和 7 的字符。
对于 "code" 的第 2 个副本，选取下标为 17 、18 、19 和 20 的字符。
形成的字符串分别是 "ecod" 和 "code" ，都可以重排为 "code" 。
可以形成最多 2 个 "code" 的副本，所以返回 2 。

示例 2：

输入：s = "abcba", target = "abc"
输出：1
解释：
选取下标为 0 、1 和 2 的字符，可以形成 "abc" 的 1 个副本。 
可以形成最多 1 个 "abc" 的副本，所以返回 1 。
注意，尽管下标 3 和 4 分别有额外的 'a' 和 'b' ，但不能重用下标 2 处的 'c' ，所以无法形成 "abc" 的第 2 个副本。

示例 3：

输入：s = "abbaccaddaeea", target = "aaaaa"
输出：1
解释：
选取下标为 0 、3 、6 、9 和 12 的字符，可以形成 "aaaaa" 的 1 个副本。
可以形成最多 1 个 "aaaaa" 的副本，所以返回 1 。

提示：

• 1 <= s.length <= 100
• 1 <= target.length <= 10
• s 和 target 由小写英文字母组成

2、思路1​

枚举计数

3、代码​

function rearrangeCharacters(s: string, target: string): number {
    let ans = Infinity;

    for (const t of target) {
        const c1 = [...s].filter(c => c === t).length;
        const c2 = [...target].filter(c => c === t).length;
        ans = Math.min(ans, c1 / c2 >> 0);
    }

    return ans;
};

4、复杂度​

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

5、执行结果​

6、思路2​

哈希计数

7、代码​

function rearrangeCharacters(s: string, target: string): number {
    const dict1 = {};
    for (const c of target) dict1[c] = (dict1[c] || 0) + 1;

    const dict2 = {};
    for (const c of s) dict2[c] = (dict2[c] || 0) + 1;

    let ans = Infinity;
    for (const k of Object.keys(dict1)) {
        ans = Math.min(ans, (dict2[k] || 0) / dict1[k] >> 0);
    }

    return ans;
};

8、复杂度​

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

9、执行结果​

1、题干​

给你一个字符串 s ，它包含一些括号对，每个括号中包含一个 非空 的键。

• 比方说，字符串 "(name)is(age)yearsold" 中，有 两个 括号对，分别包含键 "name" 和 "age" 。

你知道许多键对应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] ，表示键 keyi 对应的值为 valuei 。

你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 keyi 时，你需要：

• 将 keyi 和括号用对应的值 valuei 替换。
• 如果从 knowledge 中无法得知某个键对应的值，你需要将 keyi 和括号用问号 "?" 替换（不需要引号）。

knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。

请你返回替换 所有 括号对后的结果字符串。

示例 1：

输入：s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
输出："bobistwoyearsold"
解释：
键 "name" 对应的值为 "bob" ，所以将 "(name)" 替换为 "bob" 。
键 "age" 对应的值为 "two" ，所以将 "(age)" 替换为 "two" 。

示例 2：

输入：s = "hi(name)", knowledge = [["a","b"]]
输出："hi?"
解释：由于不知道键 "name" 对应的值，所以用 "?" 替换 "(name)" 。

示例 3：

输入：s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
输出："yesyesyesaaa"
解释：相同的键在 s 中可能会出现多次。
键 "a" 对应的值为 "yes" ，所以将所有的 "(a)" 替换为 "yes" 。
注意，不在括号里的 "a" 不需要被替换。

提示：

• 1 <= s.length <= 105
• 0 <= knowledge.length <= 105
• knowledge[i].length == 2
• 1 <= keyi.length, valuei.length <= 10
• s 只包含小写英文字母和圆括号 '(' 和 ')' 。
• s 中每一个左圆括号 '(' 都有对应的右圆括号 ')' 。
• s 中每对括号内的键都不会为空。
• s 中不会有嵌套括号对。
• keyi 和 valuei 只包含小写英文字母。
• knowledge 中的 keyi 不会重复。

2、思路1​

正则

3、代码​

function evaluate(s: string, knowledge: string[][]): string {
    const map = new Map(knowledge as Array<[string, string]>);
    return s.replace(/\(([^)]*)\)/g, (m, s1) => map.get(s1) ?? '?');
};

4、执行结果​

5、思路2​

模拟

6、代码​

function evaluate(s: string, knowledge: string[][]): string {
    const map = new Map(knowledge as Array<[string, string]>);

    let ans = '';
    for (let i = 0, l = 0, r = 0; i < s.length; i = r + 1) {
        l = s.indexOf('(', i);
        if (l < 0) {
            ans += i ? s.slice(i) : s;
            break;
        }

        r = s.indexOf(')', l);

        const w = s.slice(l + 1, r);
        ans += s.slice(i, l) + (map.get(w) ?? '?');
    }

    return ans;
};

7、复杂度​

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

8、执行结果​