DDSA Solutions

1807. Evaluate the Bracket Pairs of a String

MediumView on LeetCode
ArrayHash TableString

Problem Overview

Each bracket pair is a key lookup.

Intuition

Each bracket pair is a key lookup. The knowledge list becomes a map from key to value, then one left-to-right scan copies the plain text and replaces each (key) with its value, or with ? when the key was never given.

Algorithm

  1. 1Insert every knowledge pair into a hash map.
  2. 2Walk s. While the current character is not an opening bracket, append that plain run in one slice.
  3. 3On an opening bracket, read until the closing bracket and take the text in between as the key.
  4. 4Append the mapped value, or ? if the key is absent.
  5. 5Return the built string.

Example Walkthrough

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]

  1. 1.(name) maps to bob.
  2. 2.The letters is are copied as they are.
  3. 3.(age) maps to two, then yearsold is copied.

Output: "bobistwoyearsold"

Common Pitfalls

  • •A missing key becomes ?, not an empty string.
  • •Brackets are not nested, so the next closing bracket ends the key.
  • •Store the inner key only. The parentheses are not part of the lookup.
  • •Literal text between brackets should be appended as a slice, not one character at a time.
1807.cs
C#
// Approach: Store knowledge as key to value. Walk s once. Copy each plain
// run in one append. On '(', read until the matching ')' and look up the
// inner key, appending the value or '?' when it is missing.
// Complexity: O(n + k) time, O(k + output) space. n is the string length
// and k is the number of knowledge pairs.
public class Solution
{
    public string Evaluate(string s, IList<IList<string>> knowledge)
    {
        var map = new Dictionary<string, string>(knowledge.Count);
        foreach (var pair in knowledge)
            map[pair[0]] = pair[1];

        var sb = new StringBuilder(s.Length);
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] != '(')
            {
                int start = i;
                while (i < s.Length && s[i] != '(')
                    i++;
                sb.Append(s, start, i - start);
                i--;
                continue;
            }

            int close = i + 1;
            while (s[close] != ')')
                close++;
            string key = s.Substring(i + 1, close - i - 1);
            sb.Append(map.TryGetValue(key, out string value) ? value : "?");
            i = close;
        }

        return sb.ToString();
    }
}
Was this solution helpful?

Related Problems