> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/stack/880-decoded-string-at-index.md).

# 880     Decoded String at Index

## 880. [Decoded String at Index](https://leetcode.com/problems/decoded-string-at-index/description/)

## 1. Question

An encoded string`S`is 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 (say`d`), the entire current tape is repeatedly written `d-1`more times in total.

Now for some encoded string`S`, and an index`K`, find and return the`K`-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. `S`will only contain lowercase letters and digits`2`through`9`.
3. `S`starts with a letter.
4. `1 <= K <= 10^9`
5. The decoded string is guaranteed to have less than`2^63`letters.

## 2. Implementation

**(1) Math**

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

```java
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)