[LeetCode] 1807. Evaluate the Bracket Pairs of a String

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

• For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [keyi, valuei] indicates that key keyi has a value of valuei.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key keyi, you will:

• Replace keyi and the bracket pair with the key's corresponding valuei.
• If you do not know the value of the key, you will replace keyi and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

Constraints:

• 1 <= s.length <= 105
• 0 <= knowledge.length <= 105
• knowledge[i].length == 2
• 1 <= keyi.length, valuei.length <= 10
• s consists of lowercase English letters and round brackets '(' and ')'.
• Every open bracket '(' in s will have a corresponding close bracket ')'.
• The key in each bracket pair of s will be non-empty.
• There will not be any nested bracket pairs in s.
• keyi and valuei consist of lowercase English letters.
• Each keyi in knowledge is unique.

替换字符串中的括号内容。

给你一个字符串 s ，它包含一些括号对，每个括号中包含一个 非空 的键。
比方说，字符串 "(name)is(age)yearsold" 中，有 两个 括号对，分别包含键 "name" 和 "age" 。
你知道许多键对应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] ，表示键 keyi 对应的值为 valuei 。
你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 keyi 时，你需要：
将 keyi 和括号用对应的值 valuei 替换。
如果从 knowledge 中无法得知某个键对应的值，你需要将 keyi 和括号用问号 "?" 替换（不需要引号）。
knowledge 中每个键最多只会出现一次。s 中不会有嵌套的括号。
请你返回替换 所有 括号对后的结果字符串。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/evaluate-the-bracket-pairs-of-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是用 hashmap 存 knowledge 中的键值对，然后扫描 input 字符串，把带括号的单词拿出来，去 hashmap 里看是否有对应的键值，如果没有则以问号代替。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public String evaluate(String s, List<List<String>> knowledge) {
 3         HashMap<String, String> map = new HashMap<>();
 4         for (List<String> k : knowledge) {
 5             map.put(k.get(0), k.get(1));
 6         }
 7         
 8         StringBuilder sb = new StringBuilder();
 9         for (int i = 0; i < s.length(); i++) {
10             if (s.charAt(i) == '(') {
11                 int j = i + 1;
12                 while (i < s.length() && s.charAt(i) != ')') {
13                     i++;
14                 }
15                 String key = s.substring(j, i);
16                 if (!map.containsKey(key)) {
17                     sb.append('?');
18                 } else {
19                     sb.append(map.get(key));
20                 }
21             } else {
22                 sb.append(s.charAt(i));
23             }
24         }
25         return sb.toString();
26     }
27 }

LeetCode 题目总结