880 Decoded String at Index

880. Decoded String at Index

1. Question

An encoded stringSis given. To find and write the_decoded_string to a tape, the encoded string is read one character at a time and the following steps are taken:

• If the character read is a letter, that letter is written onto the tape.

• If the character read is a digit (sayd), the entire current tape is repeatedly written d-1more times in total.

Now for some encoded stringS, and an indexK, find and return theK-th 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".

Note:

1. 2 <= S.length <= 100

2. Swill only contain lowercase letters and digits2through9.

3. Sstarts with a letter.

4. 1 <= K <= 10^9

5. The decoded string is guaranteed to have less than2^63letters.

2. Implementation

(1) Math

思路: 一看下最简单的做法就是解析String, 然后找出第K个位置的character。但这种做法其实不需要，因为我们只关心第K个位置的character，我们只要知道解析后的string的总长度，然后从后往前扫一遍输入的String， 当K等于0， 而当前位置的character不是digit，则我们找到第K个character

class Solution {
    public String decodeAtIndex(String S, int K) {
        long len = 0;

        for (char c : S.toCharArray()) {
            if (Character.isDigit(c)) {
                len *= (c - '0');
            }
            else {
                ++len;
            }
        }

        for (int i = S.length() - 1; i >= 0; i--) {
            K %= len;

            char c = S.charAt(i);

            if (K == 0 && c >= 'a' && c <= 'z') {
                return "" + c;
            }

            if (Character.isDigit(c)) {
                len /= (c - '0');
            }
            else {
                --len;
            }
        }
        return  "";
    }
}

3. Time & Space Complexity

(1) Math: 时间复杂度O(n), 空间复杂度O(1)