Share my recursive solution, 0ms


  • 0
    T

    just use recursion to solve it, nothing fancy
    key points:

    • an encoded string might contain unencoded part. e.g., "abc" in "abc2[ab]"
    class Solution {
    public:
        string decodeString(string s) {
            int i = 0, n = s.length();
            string res;
            while (i < n) res += helper(s, i);
            return res;
        }
        //helper(s, i) will return a decoded string of a well-formed encoded string starts from s[i]
        string helper(string & s, int & i) {
            int n = s.length();
            if (i == n) return "";
            string res, tmp;
            //case 1 : regular string, e.g., "abc"
            if (!isdigit(s[i])) {
                while (i < n && !isdigit(s[i]) && s[i] != ']') res += s[i++];
                return res;
            }
            //case 2 : repeat string, e.g., "2[abc]"
            //get repeat number k
            int rep = 0;
            while (i < n && isdigit(s[i])) rep = rep * 10 + (s[i++] - '0');
            //get repeat string
            i++;//skip '['
            while (i < n && !isdigit(s[i]) && s[i] != ']') tmp += s[i++];
            while (i < n && s[i] != ']') tmp += helper(s, i);
            //make duplicates
            while (rep) {
                res += tmp;
                rep--;
            }
            //advance index
            i++;//skip ']'
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.