Leetcode 1807: Evaluate the Bracket Pairs of a String
You are given a string
s containing several bracket pairs with non-empty keys. You are also provided a 2D array knowledge where each element is a key-value pair. Your task is to evaluate the string by replacing the keys inside the bracket pairs with their corresponding values. If a key is unknown, replace it with a question mark ?.Problem
Approach
Steps
Complexity
Input: The input consists of a string `s` and a 2D array `knowledge` containing key-value pairs.
Example: s = "(user)likes(cats)", knowledge = [["user","Alice"], ["cats","dogs"]]
Constraints:
• 1 <= s.length <= 10^5
• 0 <= knowledge.length <= 10^5
• knowledge[i].length == 2
• 1 <= keyi.length, valuei.length <= 10
• The string `s` contains lowercase English letters and round brackets `(` and `)`.
Output: Return the resulting string after evaluating all the bracket pairs in `s`.
Example: Output: "Alicelikesdogs"
Constraints:
• The output should be a string where each key in a bracket pair is replaced by its corresponding value or `?` if unknown.
Goal: To evaluate all bracket pairs in the string and replace keys with their corresponding values or `?` if unknown.
Steps:
• Initialize a map to store the key-value pairs from `knowledge`.
• Iterate over the string `s` and whenever a bracket pair is encountered, extract the key.
• Check if the key is in the map, and replace it with its corresponding value or `?` if not found.
• Continue processing the string and append the modified parts to the result string.
Goal: The string `s` is at most 100,000 characters long and contains bracket pairs. The array `knowledge` contains unique key-value pairs.
Steps:
• The solution should handle both small and large inputs efficiently.
• The output string should be constructed with respect to the input size constraints.
Assumptions:
• The input string `s` will always contain valid bracket pairs.
• All keys in `knowledge` are unique.
• Input: s = "(user)likes(cats)", knowledge = [["user","Alice"], ["cats","dogs"]]
• Explanation: The key "user" has a value of "Alice" and "cats" has a value of "dogs", so the final output is "Alicelikesdogs".
• Input: s = "hello(name)", knowledge = [["name","Bob"]]
• Explanation: The key "name" has a value of "Bob", so replace the bracket pair with the value and the result is "hellobob".
Approach: We can iterate over the string `s` and for each bracket pair, we check if the key exists in the `knowledge` map. If it does, replace it with the value; otherwise, replace it with a question mark.
Observations:
• The string `s` can be large, so we need an efficient solution to process the input in linear time.
• Using a map to store the key-value pairs from `knowledge` ensures that lookups for the keys are efficient (O(1) time complexity).
Steps:
• Create a map to store key-value pairs from `knowledge`.
• Initialize a result string `res`.
• Iterate through each character of `s`. When encountering a '(', start extracting the key until encountering a ')'.
• Check if the extracted key exists in the map and replace the bracket pair with the corresponding value or '?' if the key is unknown.
• Append all characters to the result string and return it once the iteration is complete.
Empty Inputs:
• If `knowledge` is empty, all bracket pairs will be replaced by '?' in the output.
Large Inputs:
• For large values of `s` and `knowledge`, the solution must handle the input efficiently within the time and space limits.
Special Values:
• Consider edge cases like when the string `s` has no brackets or when all keys are unknown.
Constraints:
• Ensure the solution processes the string and map efficiently in O(n) time.
string evaluate(string s, vector<vector<string>>& knowledge) {
map<string, string> mp;
for(auto e: knowledge)
mp[e[0]] = e[1];
string res = "";
int i = 0;
while(i < s.size()) {
if(s[i] == '(') {
i++;
string key = "";
while(s[i] != ')') {
key += s[i];
i++;
}
if(mp.count(key)) {
res += mp[key];
// mp.erase(key);
}
else res += '?';
i++;
} else res += s[i++];
}
return res;
}
1 : Function Definition
string evaluate(string s, vector<vector<string>>& knowledge) {
This line defines the `evaluate` function which takes a string `s` and a reference to a vector of vector of strings `knowledge`.
2 : Map Initialization
map<string, string> mp;
Here, a map `mp` is declared, where each key-value pair will represent a mapping between a key (string) and its corresponding value (string) from the `knowledge` vector.
3 : Map Population
for(auto e: knowledge)
This loop iterates through each element `e` in the `knowledge` vector.
4 : Map Assignment
mp[e[0]] = e[1];
Each element `e` in `knowledge` is a pair where `e[0]` is the key and `e[1]` is the value. This line adds them to the map `mp`.
5 : Result Initialization
string res = "";
A string `res` is initialized as an empty string to store the result of the evaluation.
6 : Index Initialization
int i = 0;
An integer variable `i` is initialized to 0, which will be used to iterate through the string `s`.
7 : While Loop
while(i < s.size()) {
This while loop continues until `i` reaches the size of string `s`.
8 : Parenthesis Check
if(s[i] == '(') {
If the character at position `i` in the string `s` is an opening parenthesis, we enter this block of code to handle the placeholder.
9 : Increment i
i++;
Move to the next character in the string after the opening parenthesis.
10 : Key Initialization
string key = "";
A string `key` is initialized to an empty string. It will be used to store the key found inside the parentheses.
11 : Extract Key
while(s[i] != ')') {
This inner while loop continues extracting characters from the string until the closing parenthesis is encountered.
12 : Add Character to Key
key += s[i];
Each character encountered inside the parentheses is appended to the `key` string.
13 : Increment i (Key Extraction)
i++;
Move to the next character in the string during key extraction.
14 : End of Key Extraction
}
End of the while loop that extracts the key inside the parentheses.
15 : Check if Key Exists in Map
if(mp.count(key)) {
Check if the `key` exists in the map `mp`.
16 : Add Value to Result
res += mp[key];
If the key exists in the map, append the corresponding value from the map to the result string `res`.
17 : Add '?' for Missing Key
else res += '?';
If the key is not found in the map, append `?` to the result string `res`.
18 : Increment i (End of Parentheses)
i++;
Move past the closing parenthesis after processing the key.
19 : Handle Non-Parenthesized Characters
} else res += s[i++];
If the character is not an opening parenthesis, simply append the character to the result string `res`.
20 : Return Final Result
return res;
Return the final result string `res` after all the placeholders are processed.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution involves iterating through the string `s` and performing constant-time lookups for each key, leading to O(n) time complexity.
Best Case: O(n)
Worst Case: O(n + m)
Description: The space complexity arises from storing the string `s` and the map of `knowledge`, where n is the length of the string and m is the number of key-value pairs in `knowledge`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus