decode-str

https://leetcode.com/problems/decode-string/description/

Notes

  • strings within strings would also need to be decoded
  • the function that generates the string could be recursive since each sub-problem resembles the original problem
  • number will be positive int
  • no spaces
  • matching brackets guaranteed

    Examples

    1
    2
    3
    4
    Input:

    "abcd10[a6[zd]]"
    "14[w]100[dfg9[ik]]"

It’s really important to try several types of examples out before we jump into the final solution. One important point to note is that we need to keep passing in pos as a reference it needs to be shared across all function invocations since we are moving through the string in one pass and need to keep track of the number of characters consumed. The solution below is a step in the right direction but has some flaws as noted below.

First Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    int pos = 0;
    /*
    Parsing starts when we encounter a number
    number can be multiple digits
    We stop parsing and return generated string
    when we encounter matching `]`
    */
    string parse(string s, int& pos, int len) {
        string res;
        string rep;
        for (; pos < s.size(); pos++) {
            if (isdigit(s[pos]) {
                rep += s[pos];
            } else if (isalpha(s[pos]) {
                res += s[pos];
            // need to explicitly update position?
            } else if (s[pos++] == ']')
            {
                for (int j = 2; j <= len; j++) {
                    res += res;
                }
            } else if (s[pos++] == '[')
            {

                res += parse(s, pos, stoi(rep));
            }

        }

        return res;
    }
public:
    string decodeString(string s) {

        // if string starts with number
        // we need to compute the number
        if (isdigit(s[0])) {
            string len;
            int i = 0;
            for (; i < s.size(); i++) {
                if (s[i] == '[') {
                    len = s.substr(0,i);
                    i++;
                    break;
                }
            }
            return parse(s, i, stoi(len));

        }
        // else just use 1
        else {
            return parse(s, pos, 1);
        }

    }
};

Issues

  1. decodeString() doesn’t need that ugly logic. We can just call parse().
  2. if (s[pos++] == ']' is incorrect here since it will increment position and then check the value, which is hardly what we want.

Accepted Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    int pos = 0;
    /*
    Parsing starts when we encounter a number
    number can be multiple digits
    We stop parsing and return generated string
    when we encounter matching `]`
    */
    string parse(string s, int& pos, int len) {
        string res;
        string rep = "";
        cout <<  " at pos = " << pos << " length = " << len << endl;
        for (; pos < s.size(); pos++) {
            if (isdigit(s[pos])) {
                rep += s[pos];

            } else if (isalpha(s[pos])) {
                res += s[pos];
            // need to explicitly update position?
            } else if (s[pos] == ']')
            {
                string tmp = res;
                for (int j = 2; j <= len; j++) {
                    res += tmp;
                }
                /*
                    we need to return here since each function
                    call only deals with [...] pair.
                    any other [...] pairs within are handled
                    by a seperate invocation of this function
                */
                break;

            } else if (s[pos] == '[')
            {

                pos++;
                res += parse(s, pos, (rep != "")?stoi(rep):1);
                // need to reset rep since we may have many
                // groups
                // ex: abc[eegh]lki55[tt]
                 rep = "";

            }
            cout << "res = " << res << " rep = " << rep << endl;

        }
        cout << "ret = " << res << endl;
        return res;
    }
public:
    string decodeString(string s) {

       return parse(s, pos, 1);


    }
};