1807-替换字符串中的括号内容

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

  • 比方说，字符串 "(name)is(age)yearsold" 中，有 两个 括号对，分别包含键 "name" 和 "age" 。

你知道许多键对应的值，这些关系由二维字符串数组 knowledge 表示，其中 knowledge[i] = [keyi, valuei] ，表示键
keyi 对应的值为 valuei 。

你需要替换 所有 的括号对。当你替换一个括号对，且它包含的键为 keyi 时，你需要：

  • 将 keyi 和括号用对应的值 valuei 替换。
  • 如果从 knowledge 中无法得知某个键对应的值，你需要将 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"
**解释：** 相同的键在 s 中可能会出现多次。
键 "a" 对应的值为 "yes" ，所以将所有的 "(a)" 替换为 "yes" 。
注意，不在括号里的 "a" 不需要被替换。

提示：

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

方法一：哈希表

为了方便查找，我们将 knowledge 保存到哈希表 dict 中。字符串 s 中有四种类型的字符：

  • 字符 `(’

  • 字符 `)’

  • 不在括号内的小写字母

  • 在括号内的小写字母

我们使用 key 保存括号内的键，addKey 表示当前小写字母是否为在括号内的小写字母。遍历字符串 s，假设当前字符为 c：

  • 如果 c 等于 `(’

    说明之后的小写字母是在括号内的，令 addKey} = \text{true。

  • 如果 c 等于 `)’

    说明 key 已经结束，如果 key 在 dict 中，我们将 dict}[\textit{key}] 附加到结果字符串中，否则将字符 `?’ 附加到结果字符串中。清除字符串 key，令 addKey} = \text{false。

  • 如果 c 是小写字母

    根据 addKey 决定字符 c 应该添加到哪里。如果 addKey 为真，那么将字符 c 追加到 key 中，否则将字符 c 追加到结果字符串中。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = dict(knowledge)
        ans, start = [], -1
        for i, c in enumerate(s):
            if c == '(':
                start = i
            elif c == ')':
                ans.append(d.get(s[start + 1: i], '?'))
                start = -1
            elif start < 0:
                ans.append(c)
        return "".join(ans)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> dict;
        for (auto &kd : knowledge) {
            dict[kd[0]] = kd[1];
        }
        bool addKey = false;
        string key, res;
        for (char c : s) {
            if (c == '(') {
                addKey = true;
            } else if (c == ')') {
                if (dict.count(key) > 0) {
                    res += dict[key];
                } else {
                    res.push_back('?');
                }
                addKey = false;
                key.clear();
            } else {
                if (addKey) {
                    key.push_back(c);
                } else {
                    res.push_back(c);
                }
            }
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> dict = new HashMap<String, String>();
        for (List<String> kd : knowledge) {
            dict.put(kd.get(0), kd.get(1));
        }
        boolean addKey = false;
        StringBuilder key = new StringBuilder();
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                addKey = true;
            } else if (c == ')') {
                if (dict.containsKey(key.toString())) {
                    res.append(dict.get(key.toString()));
                } else {
                    res.append('?');
                }
                addKey = false;
                key.setLength(0);
            } else {
                if (addKey) {
                    key.append(c);
                } else {
                    res.append(c);
                }
            }
        }
        return res.toString();
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public string Evaluate(string s, IList<IList<string>> knowledge) {
        IDictionary<string, string> dict = new Dictionary<string, string>();
        foreach (IList<string> kd in knowledge) {
            dict.Add(kd[0], kd[1]);
        }
        bool addKey = false;
        StringBuilder key = new StringBuilder();
        StringBuilder res = new StringBuilder();
        foreach (char c in s) {
            if (c == '(') {
                addKey = true;
            } else if (c == ')') {
                if (dict.ContainsKey(key.ToString())) {
                    res.Append(dict[key.ToString()]);
                } else {
                    res.Append('?');
                }
                addKey = false;
                key.Length = 0;
            } else {
                if (addKey) {
                    key.Append(c);
                } else {
                    res.Append(c);
                }
            }
        }
        return res.ToString();
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
typedef struct {
    char *key;
    char *val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, const char *key) {
    HashItem *pEntry = NULL;
    HASH_FIND_STR(*obj, key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, char *key, char *val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = val;
    HASH_ADD_STR(*obj, key, pEntry);
    return true;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);             
    }
}

char * evaluate(char * s, char *** knowledge, int knowledgeSize, int* knowledgeColSize) {
    HashItem *dict = NULL;
    for (int i = 0; i < knowledgeSize; i++) {
        hashAddItem(&dict, knowledge[i][0], knowledge[i][1]);
    }
    bool addKey = false;
    int len = strlen(s);
    char key[16], *res = (char *)malloc(sizeof(char) * (len + 1));
    int keySize = 0, resSize = 0;
    memset(key, 0, sizeof(key));
    memset(res, 0, sizeof(char) * (len + 1));
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(') {
            addKey = true;
        } else if (c == ')') {
            HashItem *pEntry = hashFindItem(&dict, key);
            if (pEntry) {
                resSize += sprintf(res + resSize, "%s", pEntry->val);
            } else {
                res[resSize++] = '?';
            }
            addKey = false;
            keySize = 0;
        } else {
            if (addKey) {
                key[keySize++] = c;
                key[keySize] = '\0';
            } else {
                res[resSize++] = c;
            }
        }
    }
    hashFree(&dict);
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var evaluate = function(s, knowledge) {
    const dict = new Map();
    for (const kd of knowledge) {
        dict.set(kd[0], kd[1]);
    }
    let addKey = false;
    let key = '';
    let res = '';
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === '(') {
            addKey = true;
        } else if (c === ')') {
            if (dict.has(key)) {
                res += dict.get(key);
            } else {
                res += '?';
            }
            addKey = false;
            key = '';
        } else {
            if (addKey) {
                key += c;
            } else {
                res += c;
            }
        }
    }
    return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func evaluate(s string, knowledge [][]string) string {
    dict := map[string]string{}
    for _, kd := range knowledge {
        dict[kd[0]] = kd[1]
    }
    ans := &strings.Builder{}
    start := -1
    for i, c := range s {
        if c == '(' {
            start = i
        } else if c == ')' {
            if t, ok := dict[s[start+1:i]]; ok {
                ans.WriteString(t)
            } else {
                ans.WriteByte('?')
            }
            start = -1
        } else if start < 0 {
            ans.WriteRune(c)
        }
    }
    return ans.String()
}

复杂度分析

  • 时间复杂度：O(n + k)，其中 n 是字符串 s 的长度，k 是字符串数组 knowledge 中所有字符串的长度之和。

  • 空间复杂度：O(n + k)，其中 n 是字符串 s 的长度，k 是字符串数组 knowledge 中所有字符串的长度之和。保存哈希表 dict 和 key 分别需要 O(k) 和 O(n)。

 Comments
On this page
1807-替换字符串中的括号内容