Decode String - Javascript

user_11068392 0
Viewed 1147

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

Problem: 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"

Thanks

depth-first-search javascript
3 Answers

You could replace the string with a regular expression and get the wanted nested replacements until no more strings are available to replace.

const decodeString = string => {
let repeat
do {
    repeat = false;
    string = string.replace(/(\d+)\[([^\[\]]+)\]/g, (_, c, v) => {
        repeat = true;
        return v.repeat(c);
    });
} while (repeat);
return string;
}

console.log(decodeString("3[a]2[bc]")); // "aaabcbc"
console.log(decodeString("3[a2[c]]")); // "accaccacc"
console.log(decodeString("2[abc]3[cd]ef")); // "abcabccdcdcdef"
console.log(decodeString("abc3[cd]xyz")); // "abccdcdcdxyz"

If you wish to simplify/update/explore the expression, it's been explained on the top right panel of regex101.com. You can watch the matching steps or modify them in this debugger link, if you'd be interested. The debugger demonstrates that how a RegEx engine might step by step consume some sample input strings and would perform the matching process.

RegEx Circuit

jex.im visualizes regular expressions:

enter image description here

user_14476750

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

  • For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.
user_65533280

This function iterates through the string once, meaning its probably faster than regex.

let string = "abc3[cd]xyz"

// this function returns true or false, depending on if the given string is a digit
const isNumber = c => (c >= '0' && c <= '9')

var decode = string => {
  let result = ""
  // the main loop
  // its faster to store 'len' than it is reuse 'string.length' every iteration
  for (let i=0,len=string.length; i<len; i++) {
    
    let character = string[i];
    
    // if the current character is a number, we know we need to decrypt the next chunk
    if (isNumber(character)) {
      let repeat_int = "";
      let repeat_string = "";
      
      // we keep looping through, adding each digit of the number to 'repeat_int'
      while (character !== "[") {
        repeat_int += character;
        i++;
        character = string[i];
      }
      
      // we need to jump ahead one extra character to avoid including "[" in the string
      i++;
      character = string[i];
      
      // we keep looping through, adding each character of the string to 'repeat_string'
      while (character !== "]") {
        repeat_string += character;
        i++;
        character = string[i];
      }
      
      // we repeat 'repeat_string' by 'repeat_int' times, and add it to the result
      result += repeat_string.repeat(repeat_int);


    // if the current character is a letter, we can simply add it to the result
    } else {
      result += character;
    }
  }
  return result;
}
user_90639350
Related