394 Decode String

Given an encoded string, return it's decoded string.

The encoding rule is:k[encoded_string], where theencoded_stringinside the square brackets is being repeated exactlyktimes. Note thatkis guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,k. For example, there won't be input like3aor2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

string go(string s, int &pos)
{
    string mult_s = "";     // default multiplier 
    string word = "";       // default substr
    for (; pos < s.length(); pos++) {
        if (s[pos] == '[') {
            string sub_word = go(s, ++pos);
            int mult_i = stoi(mult_s.c_str());
            for (mult_i; mult_i > 0; mult_i--)
                word += sub_word;
            mult_s = "";
        }

        else if (s[pos] == ']')
            return word;

        else if (isalpha(s[pos])) 
            word += s[pos];

        else if (isdigit(s[pos])) 
            mult_s += s[pos];

    }
    return word;
}


string decodeString(string s)
{
    int pos = 0;
    return go(s, pos);
}

Brain Storm

• From an earlier exercise, I understood that using a stack in a natural way of balancing out matching parenthesis. So I expanded this idea into DFS recursion.

• A subproblem in our case would be all the subproblems within []. So [ in an indicator for an additional subproblem (recurse), and ] is an indicator for the closing of a subproblem (return back). But what we return back we have to merge with the previous string. In our case, the merge step means grabbing the substring, performing the string arithmetic, and adding it to the previous string.

• With a divide and conquer algorithm, we are interested in a few things.

  • How does the recursive tree structure look like?

  • When do I return, and when do I recurse (how can I define a subproblem?), what do I return?

  • What is my merge step back to the main problem, or larger subproblem?

  • How can I solve this for a single instance (one subproblem)?