decodeString codefights: Program doesn't pass

问题:

function decodeString(s)
{
    let arr = [];
    let digitSum = '';
    let digitSumArr = []; // for numbers before '['
    let i; 

    //iterating string
    for (i = 0; i < s.length; i++)
    {
        if (!isNaN(s[i]))
        {
            digitSum += s[i]; // count number before '['
        }
        else if (s[i] === '[')
        {
            // add number to the array
            digitSumArr.push(+digitSum); 
            arr.push(i + 1);
            digitSum = '';
        }
        else if (s[i] === ']')
        {

            let digit = digitSumArr.pop();
            i = decStr(arr, i, digit);

            digitSum = '';
        }
        else
        {
            digitSum = '';
        }

    }

    return s;

    function decStr(arr, j, number)
    {
        let arrLen = arr.length;
        let n = number;
        let str = s.slice(arr[arrLen - 1], j);
        let sumStr = str;
        while (n-- > 1)
        {
            sumStr = sumStr.concat(str);
        }

        str = number + '[' + str + ']';

        s = s.replace(str, sumStr);

        arr.splice(arrLen - 1, 1);

        //return position for iterating

      return j + sumStr.length - str.length - 1; 
      }
}

Given an encoded string, return its corresponding decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note: k is guaranteed to be a positive integer.

Note that your solution should have linear complexity because this is what you will be asked during an interview.

回答1:

The problem is that the failed test has an input of sufficient complexity to require more time to solve than the allotted limit, given your solution. So, you need to find a more efficient solution.

I ran a performance benchmark on your solution and on another solution which used recursive procedure calls, and yours was 33% slower. I suggest you refactor your solution to call your parsing procedure recursively when you encounter nested iterations.