【Leetcode】880. Decoded String at Index

青旅半醒 2022-04-15 01:11 152阅读 0赞

1.  Decoded String at Index

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.

### 解析 ###

从题目的意思来看，我们可以很容易的使用暴力破解的方式来解决，但是可以肯定的是会超时。接下来我们选择逆向思维来解题，由于该题每次碰到`数字`都会将前面一段字符串重复`d-1`次，也就是说，每次遇见`数字`，那么`数字`之前的的字符串会重复`d`次。那么我们这样一来我们就可以将所得的结果分成`d`等份，这样每个等份的结果都是一样的。

在这里还需要提到一个特性：如果一个单词的长度为n，它重复x此，那么我们在这个单词组成的字符串中，任意`K`与`K%n`的结果都一样。

**举个栗子:**

字符串`leetleetleetleetleetleet`,对于单词`leet`来说重复`6`次，我们取`K=3`，那么`3%4`与`K=3`的结果是一样的。利用这些特性我们可以使用逆向思维的方式，将字符串逐渐缩小范围求解，如果我们求`k`那么可以转换为`K%n`，这样一步一步我们就可以不用考虑内存，考虑时间问题。

首先我们需要先求出字符串的长度，出现数字直接做乘法，否则我们自增。

然后我们对初始字符串进行倒序遍历，由于题目的设定，我们最后一位肯定是数字，那么我们可以认为，之前的字符串重复`d`次，这样我们可以利用上面的特性对所求的字符串进行缩减`K%n`。我们所求的目标K一定在第一个重复的字符串中，以题目例子来说:

`leet2code3`\->`leetleetcodeleetleetcodeleetleetcode` 缩减一下

`leetleetcode` k一定是在这个字符串中，因为`k`与`k%n`结果等价。

由于上述操作我们实际上是截去了一部分字符串，将重复的`n`次截取掉了`n-1`次，接下来就需要缩减size了，这对于求size是一个逆向的过程，所以我们遇见字符串就`自减`，遇见数字做除法。

然后重复我们之前的操作，对于`k`缩减为`K%n`，一直到满足`K`缩减为0，且它必须是一个字符。

当`k=10`，针对`leetleetcode`来说，`K==K%10`，因为此时K小于了单词的长度，所以起不到截取的目的，不能够缩小检索的范围，所以我们可以为了缩小范围，我们从后面开始遍历，对于非数字自减，这样我们就可以缩小`size`的范围，且不影响`K`，当`k==size`则满足我们的要求。正面检索到了我们需要的位置。

### 代码 ###

public static String decodeAtIndex(String S, int K) { 
            long size = 0;
            int N = S.length();
    
            for (int i = 0; i < N; ++i) { 
                char c = S.charAt(i);
                if (Character.isDigit(c))
                    size *= c - '0';
                else
                    size++;
            }
    
            for (int j = N - 1; j >= 0; --j) { 
                char s = S.charAt(j);
                K %= size;
                if (K == 0 && Character.isLetter(s)) { 
                    return Character.toString(s);
                }
    
                if (Character.isDigit(s)) { 
                    size /= (s - '0');
                } else { 
                    size--;
                }
            }
            return null;
        }