Medium

题目描述

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

例如，在字符串 "(name)is(age)yearsold" 中，有两个括号对分别包含键 "name" 和 "age"。

已知很多键的对应值，这用一个二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] 表示键 keyi 对应的值是 valuei。

你的任务是对所有的括号对求值。当对包含键 keyi 的括号对求值时，你需要：

  • 将 keyi 和括号对替换为键对应的值 valuei
  • 如果你不知道键的值，就将 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"
解释：同一个键可以出现多次。
键 "a" 对应的值是 "yes"，所以将所有的 "(a)" 都替换为 "yes"。
注意不在括号对中的 "a" 不会被替换。

提示：

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

解题思路

这是一个字符串处理问题，需要识别括号对并替换其中的键值。

思路分析：

  1. 预处理知识库：将 knowledge 转换为哈希表，便于快速查找键对应的值。

  2. 遍历字符串：逐个字符遍历字符串 s，使用状态机的思想：

    • 当遇到 '(' 时，开始记录括号内的键
    • 当遇到 ')' 时，结束记录并查找对应的值进行替换
    • 普通字符直接添加到结果中

  3. 替换逻辑：

    • 如果在哈希表中找到对应的键，替换为其值
    • 如果找不到，替换为 "?"

算法步骤：

  1. 构建键值映射的哈希表
  2. 遍历字符串，维护当前状态（在括号内/外）
  3. 根据状态处理字符：括号外直接添加，括号内收集键名
  4. 遇到右括号时查表替换并重置状态

这种方法时间复杂度为 O(n + m)，其中 n 是字符串长度，m 是 knowledge 数组长度，空间复杂度为 O(m) 用于存储哈希表。

代码实现

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> map;
        for (auto& pair : knowledge) {
            map[pair[0]] = pair[1];
        }
        
        string result = "";
        string key = "";
        bool inBracket = false;
        
        for (char c : s) {
            if (c == '(') {
                inBracket = true;
                key = "";
            } else if (c == ')') {
                inBracket = false;
                if (map.find(key) != map.end()) {
                    result += map[key];
                } else {
                    result += "?";
                }
            } else {
                if (inBracket) {
                    key += c;
                } else {
                    result += c;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        knowledge_map = {k: v for k, v in knowledge}
        
        result = []
        key = []
        in_bracket = False
        
        for c in s:
            if c == '(':
                in_bracket = True
                key = []
            elif c == ')':
                in_bracket = False
                key_str = ''.join(key)
                result.append(knowledge_map.get(key_str, '?'))
            else:
                if in_bracket:
                    key.append(c)
                else:
                    result.append(c)
        
        return ''.join(result)

public class Solution {
    public string Evaluate(string s, IList<IList<string>> knowledge) {
        var map = new Dictionary<string, string>();
        foreach (var pair in knowledge) {
            map[pair[0]] = pair[1];
        }
        
        var result = new StringBuilder();
        var key = new StringBuilder();
        bool inBracket = false;
        
        foreach (char c in s) {
            if (c == '(') {
                inBracket = true;
                key.Clear();
            } else if (c == ')') {
                inBracket = false;
                string keyStr = key.ToString();
                if (map.ContainsKey(keyStr)) {
                    result.Append(map[keyStr]);
                } else {
                    result.Append("?");
                }
            } else {
                if (inBracket) {
                    key.Append(c);
                } else {
                    result.Append(c);
                }
            }
        }
        
        return result.ToString();
    }
}

var evaluate = function(s, knowledge) {
    const map = new Map();
    for (const [key, value] of knowledge) {
        map.set(key, value);
    }
    
    let result = '';
    let i = 0;
    
    while (i < s.length) {
        if (s[i] === '(') {
            let j = i + 1;
            while (s[j] !== ')') {
                j++;
            }
            const key = s.substring(i + 1, j);
            result += map.has(key) ? map.get(key) : '?';
            i = j + 1;
        } else {
            result += s[i];
            i++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n + m)
空间复杂度O(m + k)

其中：

  • n 是字符串 s 的长度
  • m 是 knowledge 数组的长度
  • k 是所有键值对的总字符数

时间复杂度：需要遍历字符串 s 一次 O(n)，构建哈希表 O(m) 空间复杂度：哈希表存储 O(m)，结果字符串最坏情况 O(n + k)

相关题目