Finite-State-Machines (FSM) and avoidance of string manipulation via lazy appending

Latest problem from Leetcode required a combination of FSM and avoidance of string manipulation (in C#, expensive). Here it is: Evaluate the Bracket Pairs of a String - LeetCode

1807. Evaluate the Bracket Pairs of a String

Medium

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.

 

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 <= 105
• 0 <= knowledge.length <= 105
• knowledge[i].length == 2
• 1 <= keyi.length, valuei.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.
• keyi and valuei consist of lowercase English letters.
• Each keyi in knowledge is unique.

Accepted

3,865

Submissions

5,745

My strategy was the following:

A. Push the knowledge key/value into a hash table for quick access

B. Use an FSM with two states: "inside" a key, and "outside" a key

C. My first implementation had a lot of string concatenation - that turned out to be expensive and led to TLE

D. The strategy is to do a "lazy" appending of the strings: keep track of the indexes, and only when the state changes, do the appending

E. The first attempt was a TLE as seen below. The second one had a bug (corner case), and the third one worked fine

Code is below. Cheers, ACC.

public string Evaluate(string s, IList> knowledge)
{
    Hashtable map = new Hashtable();

    foreach (List pair in knowledge)
    {
        string key = pair[0];
        string value = pair[1];

        if (!map.ContainsKey(key)) map.Add(key, value);
    }

    string retVal = "";
    bool insideKey = false;
    int initChunk = 0;
    int endChunk = -1;
    int initKey = 0;
    int endKey = -1;

    for (int i = 0; i < s.Length; i++)
    {
        if (s[i] == '(')
        {
            //Copy the chunk, if there is one
            if (endChunk >= initChunk && (i - 1 < 0 || s[i - 1] != ')'))
            {
                retVal += s.Substring(initChunk, endChunk - initChunk + 1);
            }
            initKey = i + 1;
            endKey = i + 1;
            insideKey = true;
        }
        else if (s[i] == ')')
        {
            //Copy the key, if it exists
            if (endKey >= initKey)
            {
                string currentKey = s.Substring(initKey, endKey - initKey + 1);
                if (map.ContainsKey(currentKey)) retVal += (string)map[currentKey];
                else retVal += "?";
            }
            initChunk = i + 1;
            endChunk = i + 1;
            insideKey = false;
        }
        else
        {
            if (insideKey)
            {
                endKey = i;
            }
            else
            {
                endChunk = i;
            }
        }
    }

    if (endChunk >= initChunk && initChunk < s.Length)
    {
        retVal += s.Substring(initChunk, endChunk - initChunk + 1);
    }

    return retVal;
}