880. Decoded String at Index

Difficulty:
Related Topics:
Similar Questions:

    Problem

    You are given an encoded string s. To decode the string to a tape, the encoded string is read one character at a time and the following steps are taken:

    Given an integer k, return **the *kth* letter (1-indexed) in the decoded string**.

      Example 1:

    Input: s = "leet2code3", k = 10
    Output: "o"
    Explanation: The decoded string is "leetleetcodeleetleetcodeleetleetcode".
    The 10th letter in the string is "o".
    

    Example 2:

    Input: s = "ha22", k = 5
    Output: "h"
    Explanation: The decoded string is "hahahaha".
    The 5th letter is "h".
    

    Example 3:

    Input: s = "a2345678999999999999999", k = 1
    Output: "a"
    Explanation: The decoded string is "a" repeated 8301530446056247680 times.
    The 1st letter is "a".
    

      Constraints:

    Solution

    /**
     * @param {string} s
     * @param {number} k
     * @return {string}
     */
    var decodeAtIndex = function(s, k) {
        var totalMap = Array(s.length);
        for (var i = 0; i < s.length; i++) {
            if (isDigit(s[i])) {
                totalMap[i] = Number(s[i]) * totalMap[i - 1];
            } else {
                totalMap[i] = (totalMap[i - 1] || 0) + 1;
            }
            if (totalMap[i] >= k) {
                return helper(s, k, totalMap, i);
            }
        }
    };
    
    var helper = function(s, k, totalMap, i) {
        if (isDigit(s[i])) {
            if (totalMap[i] === k || k % totalMap[i - 1] === 0) {
                var j = i - 1;
                while (isDigit(s[j])) j--;
                return s[j];
            } else {
                var n = k % totalMap[i - 1];
                return helper(s, n, totalMap, i - 1);
            }
        } else {
            if (totalMap[i] === k) {
                return s[i];
            } else {
                return helper(s, k, totalMap, i - 1);
            }
        }
    };
    
    var isDigit = function(char) {
        return char >= '2' && char <= '9';
    };
    

    Explain:

    nope.

    Complexity: