替换字符串中的括号内容【LC1807】

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.

不看题目 直接看示例更快

• 思路：

。为了快速替换，使用哈希表存储键值和对应的value值。

。如果当前字符不是左括号，那么将其直接放入结果末尾；如果是左括号，那么搜索括号内的单词，然后进行替换。

。替换规则为：如果哈希表内存在该单词，则替换为value值，不存在则替换为"?"

• 思路

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        int n = s.length();
        Map<String,String> map = new HashMap<>();
        for (List<String> list : knowledge){
            map.put(list.get(0), list.get(1));
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++){
            if (s.charAt(i) != '('){
                sb.append(s.charAt(i));
            }else{
                int j = i + 1;
                while(s.charAt(j) != ')'){
                    j++;
                }
                sb.append(map.getOrDefault(s.substring(i + 1, j), "?"));
                i = j;
            }
        }
        return sb.toString();
    }
}

。复杂度

• 时间复杂度：O ( n ) ，n为字符串长度
• 空间复杂度：O ( m ) ，m为数组的大小