Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1807.html

1807. Evaluate the Bracket Pairs of a String

Level

Medium

Description

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] = [key_i, value_i] indicates that key key_i has a value of value_i.

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

  • Replace key_i and the bracket pair with the key’s corresponding value_i.
  • If you do not know the value of the key, you will replace key_i 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.

Example 4:

Input: s = “(a)(b)”, knowledge = [[“a”,”b”],[“b”,”a”]]

Output: “ba”

Constraints:

  • 1 <= s.length <= 10^5
  • 0 <= knowledge.length <= 10^5
  • knowledge[i].length == 2
  • 1 <= key_i.length, value_i.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.
  • key_i and value_i consist of lowercase English letters.
  • Each key_i in knowledge is unique.

Solution

First use a map to store all key-value pairs in knowledge. Then loop over s and generate the evaluated string. If the current position is out of brackets, simply append the current character to the evaluated string. Otherwise, find the key, get the value from the map and append the value to the evaluated string, or append "?" to the evaluated string if the key does not exist in the map. Finally, return the evaluated string.

  • class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<String, String>();
        for (List<String> entry : knowledge) {
            String key = entry.get(0), value = entry.get(1);
            map.put(key, value);
        }
        StringBuffer sb = new StringBuffer();
        boolean inBracket = false;
        int start = -1;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                inBracket = true;
                start = i + 1;
            } else if (c == ')') {
                inBracket = false;
                String key = s.substring(start, i);
                String value = map.getOrDefault(key, "?");
                sb.append(value);
            } else if (!inBracket)
                sb.append(c);
        }
        return sb.toString();
    }
}

############

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> d = new HashMap<>(knowledge.size());
        for (var e : knowledge) {
            d.put(e.get(0), e.get(1));
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                int j = s.indexOf(')', i + 1);
                ans.append(d.getOrDefault(s.substring(i + 1, j), "?"));
                i = j;
            } else {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }
}

  • // OJ: https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string/
// Time: O(S + A)
// Space: O(S + A)
class Solution {
public:
    string evaluate(string s, vector<vector<string>>& A) {
        unordered_map<string, string> m;
        for (auto &v : A) {
            m[v[0]] = v[1];
        }
        int N = s.size(), start = -1;
        string ans;
        for (int i = 0; i < N; ++i) {
            if (s[i] == '(') {
                start = i;
            } else if (s[i] == ')') {
                auto key = s.substr(start + 1, i - start - 1);
                if (m.count(key)) ans += m[key];
                else ans += "?";
                start = -1;
            } else if (start == -1) {
                ans += s[i];
            }
        }
        return ans;
    }
};

  • class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        d = {a: b for a, b in knowledge}
        i, n = 0, len(s)
        ans = []
        while i < n:
            if s[i] == '(':
                j = s.find(')', i + 1)
                ans.append(d.get(s[i + 1 : j], '?'))
                i = j
            else:
                ans.append(s[i])
            i += 1
        return ''.join(ans)

############

# 1807. Evaluate the Bracket Pairs of a String
# https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        mp = {k:v for k,v in knowledge}
        res = []
        key = ""
        going = False
        
        for i,x in enumerate(s):
            if x == "(":
                going = True
            elif x == ")":
                going = False
                res.append(mp.get(key, "?"))
                key = ""
            elif going:
                key += x
            else:
                res.append(x)
        
        return "".join(res)


  • func evaluate(s string, knowledge [][]string) string {
	d := map[string]string{}
	for _, v := range knowledge {
		d[v[0]] = v[1]
	}
	var ans strings.Builder
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			j := i + 1
			for s[j] != ')' {
				j++
			}
			if v, ok := d[s[i+1:j]]; ok {
				ans.WriteString(v)
			} else {
				ans.WriteByte('?')
			}
			i = j
		} else {
			ans.WriteByte(s[i])
		}
	}
	return ans.String()
}

  • function evaluate(s: string, knowledge: string[][]): string {
    const n = s.length;
    const map = new Map();
    for (const [k, v] of knowledge) {
        map.set(k, v);
    }
    const ans = [];
    let i = 0;
    while (i < n) {
        if (s[i] === '(') {
            const j = s.indexOf(')', i + 1);
            ans.push(map.get(s.slice(i + 1, j)) ?? '?');
            i = j;
        } else {
            ans.push(s[i]);
        }
        i++;
    }
    return ans.join('');
}


  • use std::collections::HashMap;
impl Solution {
    pub fn evaluate(s: String, knowledge: Vec<Vec<String>>) -> String {
        let s = s.as_bytes();
        let n = s.len();
        let mut map = HashMap::new();
        for v in knowledge.iter() {
            map.insert(&v[0], &v[1]);
        }
        let mut ans = String::new();
        let mut i = 0;
        while i < n {
            if s[i] == b'(' {
                i += 1;
                let mut j = i;
                let mut key = String::new();
                while s[j] != b')' {
                    key.push(s[j] as char);
                    j += 1;
                }
                ans.push_str(map.get(&key).unwrap_or(&&'?'.to_string()));
                i = j;
            } else {
                ans.push(s[i] as char);
            }
            i += 1;
        }
        ans
    }
}

All Problems

All Solutions