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

括号里的键换成值，拼出完整结果串

给一个字符串 s，只有小写字母和成对、不嵌套的小括号，每对括号里是一个非空的键。另给清单 knowledge，每项是「键，值」。要把 s 里每对括号连同键换成对应的值，查不到的键整对换成一个问号，括号外的字母原样保留。题面 s = "(name)is(age)yearsold"，name 对应 bob、age 对应 two，得到 "bobistwoyearsold"。

每查一个键都翻遍清单，慢在哪

不建表的话，收出括号里的键后，就得到 knowledge 里从头找哪项的键和它一样。可 s 里可能有很多对括号，每对都把清单从头翻一遍。设 s 长 n、清单键值总字符数是 m，括号对数最多到 n 量级、每次线性找又是 m 量级，乘起来接近 n 乘 m，键一多、清单一长就拖慢。症结在「按键找值」每回都白翻，翻一次记下就够。

先建一张表，把查键做成一步到位

把 knowledge 一次性搬进哈希表，也就是按键直接拿到值的那种表。表建好后不论查多少次键都是常数时间，不必再回原清单里翻。

剩下的事是从左到右把 s 扫一遍：遇到括号外的字母直接抄进结果；遇到左括号，就从下一个字符起把键一个个收起来，直到撞见右括号，再拿整段键去表里查——查到就把这对括号换成对应的值，查不到就换一个问号。一趟扫完，结果串就拼好了。

指针为什么一趟扫到底，不用回头

括号不嵌套、每个左括号都配一个右括号，这两条保证扫描不必回头。参考代码里下标 i 从头走到末尾：s 当前位不是左括号就把字母接进结果；是左括号就用 find 找到配对的右括号位置 j，把两括号之间那段当键去查表、把查到的接进结果，再让 i 直接跳到 j 后接着走。每段括号一次处理完、指针不倒退，整趟就是线性的。收键要把括号里整段收全再查，只取头一个字符会把多字符的键查错。

(name)is(age)yearsold 扫到最后拼成什么

先建表，记下 name 对应 bob、age 对应 two。指针从下标 0 出发：先撞上左括号，收键收到 name，到右括号闭合，查表得 bob，结果是 "bob"。接着 i、s 两个字母在括号外，原样抄上成 "bobis"。再遇左括号，收键 age，查表得 two，拼成 "bobistwo"。最后 yearsold 全在括号外逐个抄进去，得到 "bobistwoyearsold"。若换成 s = "hi(name)"、清单里查不到 name，这对括号就换成问号、hi 原样保留，结果是 "hi?"。

两段都线性，剩几个坑要防

建表把 knowledge 的 m 个字符过一遍，扫描把 s 的 n 个字符过一遍，查表平均常数时间，相加是 O(n+m)。空间上哈希表存下所有键值是 O(m)、拼结果的容器和输出等长是 O(n)，峰值取两者之和 O(n+m)，不是常数。

查不到的键必须换成一个问号，留空会漏字符、保留原键会把括号或键名混进结果。括号外的字母只能原样抄，别也拿去查表，像 (a)(a)aaa 里括号中的 a 要换值、后面裸着的三个 a 得原样留着。同一个键出现几次就各查各换，别只换第一次。

Python

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)

C++

#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;
    }
};

Java

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();
    }
}