替换字符串中的括号内容 图解题解

这道题到底在问什么

输入

s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]

输出

"bobistwoyearsold"（name 换 bob、age 换 two,中间字母不动）

输入

s = "hi(name)", knowledge = [["a","b"]]

输出

"hi?"（清单里没有 name,这对括号换成问号）

最优解：一步一步想明白

1. 3记住这套动作:先建表,再一遍扫。括号外的字母照抄,括号内的字符拼成键去查表,查到用值替换、查不到用问号替换。下面每一帧都在套这个流程,先看建表,再看指针一格一格往右走。
2. 4先看清这串 "z(a)(a)(bc)" 的结构。开头的 z 在括号外,是要原样保留的普通字母;后面是三对括号,里面的键分别是 a、a、bc。绿色标出的是括号内的键、灰色是括号本身。心里有了这张地图,再开始建表和扫描。
3. 5正式扫描前,先把 knowledge 这张清单搬进哈希表。现在表还空着,一条都没有。建表的好处是,后面不管查多少次键,每次都是常数时间,不用每次都在原始清单里从头找一遍。
4. 6knowledge 的第一条是键 a 对应值 go,放进表里。以后只要在括号里读到键 a,一查表就能拿到 go。
5. 7第二条是键 k 对应值 hi,也放进表里。注意这条 k 在待处理的字符串里其实一次都用不上,但表里存着不碍事,查不到才是问题,查得到用不到没关系。
6. 8表建好了,一共两条。现在把指针放回字符串开头,准备从下标 0 开始一格一格往右扫。结果串目前是空的,接下来会一点点拼出来。
7. 9指针在下标 0,这是括号外面的普通字母 "z"。不用查表,直接原样抄进结果。结果串现在是 "z"。
8. 10指针走到下标 1,这是一个左括号。看到左括号就知道:接下来一段是括号里的键。先把键的缓冲清空,从下一格开始一个字符一个字符地把键收进来,直到撞见右括号为止。
9. 11指针在括号里,读到字符 "a",把它接到键的缓冲上,现在收集到的键是 "a"。还没到右括号,继续往右收,看键会不会更长。
10. 12指针走到下标 3 的右括号,这对括号闭合了。中间收集到的键是 "a"。现在拿这个键去知识表里查一下,看看表里有没有这一行。
11. 13表里正好有键 "a" 这一行,对应的值是 "go"。于是把左括号、键、右括号这一整对,统统换成 "go" 接到结果后面。现在结果串变成 "zgo"。
12. 14指针走到下标 4,这是一个左括号。看到左括号就知道:接下来一段是括号里的键。先把键的缓冲清空,从下一格开始一个字符一个字符地把键收进来,直到撞见右括号为止。
13. 15指针在括号里,读到字符 "a",把它接到键的缓冲上,现在收集到的键是 "a"。还没到右括号,继续往右收,看键会不会更长。
14. 16指针走到下标 6 的右括号,这对括号闭合了。中间收集到的键是 "a"。现在拿这个键去知识表里查一下,看看表里有没有这一行。
15. 17表里正好有键 "a" 这一行,对应的值是 "go"。于是把左括号、键、右括号这一整对,统统换成 "go" 接到结果后面。现在结果串变成 "zgogo"。
16. 18指针走到下标 7,这是一个左括号。看到左括号就知道:接下来一段是括号里的键。先把键的缓冲清空,从下一格开始一个字符一个字符地把键收进来,直到撞见右括号为止。
17. 19指针在括号里,读到字符 "b",把它接到键的缓冲上,现在收集到的键是 "b"。还没到右括号,继续往右收,看键会不会更长。
18. 20指针在括号里,读到字符 "c",把它接到键的缓冲上,现在收集到的键是 "bc"。还没到右括号,继续往右收,看键会不会更长。
19. 21指针走到下标 10 的右括号,这对括号闭合了。中间收集到的键是 "bc"。现在拿这个键去知识表里查一下,看看表里有没有这一行。
20. 22拿这个键到哈希表里查一次,发现没有 "bc" 这个键。按规则,查不到的键要用一个问号来替换,而不是留空或保留原样。于是这对括号换成 "?" 接到结果后面,结果串变成 "zgogo?"。
21. 23指针走到字符串末尾,整个 s 只扫了一遍,每个字符都处理过了。括号外的字母原样抄,括号内的键查表替换,结果串一路拼到现在是 "zgogo?"。
22. 24回放一遍怎么拼出来的:开头的 z 在括号外,原样保留;第一对 (a) 查到 go、第二对 (a) 同一个键还是查到 go,同一个键出现两次都替换;最后 (bc) 在表里查不到,换成一个问号。连起来正好是 "zgogo?"。
23. 25最后对照一下规则有没有走偏:括号外的字母原样保留、括号内的键查到就用值替换、查不到就用一个问号替换,同一个键出现几次就替换几次。演示这三种情况都碰上了,答案 "zgogo?" 完全符合规则。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = {a: b for a, b in knowledge}
        i, n = 0, len(s)
        ans = []
        while i < n:
            if s[i] == '(':
                j = s.find(')', i + 1)
                ans.append(d.get(s[i + 1 : j], '?'))
                i = j
            else:
                ans.append(s[i])
            i += 1
        return ''.join(ans)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> d;
        for (auto& e : knowledge) {
            d[e[0]] = e[1];
        }
        string ans;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                int j = s.find(")", i + 1);
                auto t = s.substr(i + 1, j - i - 1);
                ans += d.count(t) ? d[t] : "?";
                i = j;
            } else {
                ans += s[i];
            }
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> d = new HashMap<>(knowledge.size());
        for (List<String> e : knowledge) {
            d.put(e.get(0), e.get(1));
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                int j = s.indexOf(')', i + 1);
                ans.append(d.getOrDefault(s.substring(i + 1, j), "?"));
                i = j;
            } else {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

复杂度

面试官可能追问