javascriptdepth-first-search

Decode a run-length encoded string

I'm trying to implement the Decode String algorithm in javascript.

The LeetCode Problem 394. Decode String is:

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is 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 like 3a or 2[4].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]" Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

My attempt:

var decodeString = function(s) {
    if(!s || s.length === 0)    return "";
    
    let map = {
        '0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6,
        '7': 7, '8': 8, '9': 9
    };
    let res = "";
    
    const dfs = (str) => {
        //let res = "";
        const arr = str.split("");
        for(let i=0; i<arr.length; i++) {
            if(arr[i] === '[') {
                // call dfs
                const close = getClosePos(i, arr);
                dfs(arr.splice(i+1,close-(i+1)).join(""));
            } else if(map[arr[i]] !== undefined) {
                // repet N next letters
                let k = map[arr[i]];
                while(k > 0) {
                    res += dfs(arr.splice(i+1,arr.length).join(""));
                    k--;
                }
            } else if(arr[i] !== ']') {
                res += arr[i];
            }
        }
        //return res;
    }
    dfs(s);
    
    return res;
};

const getClosePos = (i, arr) => {
    for(let j=i; j<arr.length; j++) {
        if(arr[j] === ']')
            return j;
    }
    return 0;
}

My output is: "undefinedundefinedundefined"

Solution

  • This answer is creative and good; we can also use stack for solving this problem.

    This'll get accepted:

    const decodeString = s => {
    const stack = [];
    for (const char of s) {
        if (char !== "]") {
            stack.push(char);
            continue;
        }

        let currChar = stack.pop();
        let decoded = '';
        while (currChar !== '[') {
            decoded = currChar.concat(decoded);
            currChar = stack.pop();
        }

        let num = '';
        currChar = stack.pop();

        while (!Number.isNaN(Number(currChar))) {
            num = currChar.concat(num);
            currChar = stack.pop();
        }

        stack.push(currChar);
        stack.push(decoded.repeat(Number(num)));
    }

    return stack.join('');
};

console.log(decodeString("3[a]2[bc]"))
console.log(decodeString("3[a2[c]]"))
console.log(decodeString("2[abc]3[cd]ef"))
console.log(decodeString("abc3[cd]xyz"))

    In Python, we would similarly use a list, which is very similar to JavaScript's array:

    class Solution:
    def decodeString(self, base_string):
        stack = []
        decoded = ''
        full_num = 0

        for char in base_string:
            if char == '[':
                stack.append(decoded)
                stack.append(full_num)
                decoded, full_num = '', 0
            elif char == ']':
                curr_digit, curr_char = stack.pop(), stack.pop()
                decoded = curr_char + curr_digit * decoded
            elif char.isdigit():
                full_num *= 10
                full_num += int(char)
            else:
                decoded += char

        return decoded

    In Java, we would have used two Stacks:

    class Solution {
    public String decodeString(String string) {
        String decoded = "";
        Stack<Integer> numberStack = new Stack<>();
        Stack<String> decodedStack = new Stack<>();
        int count = 0;

        while (count < string.length()) {
            if (Character.isDigit(string.charAt(count))) {
                int fullNum = 0;

                while (Character.isDigit(string.charAt(count))) {
                    fullNum = 10 * fullNum + (string.charAt(count) - '0');
                    count++;
                }

                numberStack.push(fullNum);

            } else if (string.charAt(count) == '[') {
                decodedStack.push(decoded);
                decoded = "";
                count++;

            } else if (string.charAt(count) == ']') {
                StringBuilder temp = new StringBuilder(decodedStack.pop());
                int repeatTimes = numberStack.pop();

                for (int iter = 0; iter < repeatTimes; iter++)
                    temp.append(decoded);

                decoded = temp.toString();
                count++;

            } else
                decoded += string.charAt(count++);
        }

        return decoded;
    }
}

    References