题目
概述：给定一个字符串，将其编码成另一个字符串，编码规则：字母不变，数字则将当前已经编码的字符串重复（数字大小-1）次。给定一个索引，输出编码后字符串对应索引的字符
-
输入：
- 字符串，长度范围[2, 100]，由字母开头，且仅由小写英文字母和数字2~9组成
- 索引，大小范围[1, 10^9]
解码后的字符串长度不会超过2^63
输出：编码后字符串指定索引处的字符
出处：https://leetcode-cn.com/problems/decoded-string-at-index/
思路
- 遍历字符串，记录当前字符串编码后字符串的长度，并记录当前编码后字符串长度到当前字符的映射，如果当前字符是数字，则这次映射的字符与上一次相同
- 当遍历到当前字符串的长度大于等于索引时，重新计算索引=（索引-上一次字符串长度）% 上一次字符串长度（索引等于0时应加上上一次字符串长度），重新遍历字符串直至当前字符串的长度等于索引
- 根据最终计算的索引从一开始记录的映射表中取出对应字符
代码
class Solution {
public String decodeAtIndex(String S, int K) {
char[] sArray = S.toCharArray();
Map<Long, Character> map = new HashMap<>();
long ind = K;
long len, lastLen;
boolean isFirst = true;
while (true) {
len = 0L;
lastLen = 0L;
for (int i = 0; ;++i) {
if (sArray[i] >= 'a' && sArray[i] <= 'z') {
++len;
if (isFirst) {
map.put(len, sArray[i]);
}
} else {
len *= (sArray[i] - '0');
if (isFirst) {
map.put(len, map.get(lastLen));
}
}
// check len before forward lastLen
if (len >= ind) {
break;
}
lastLen = len;
}
if (len == ind) {
return "" + map.get(len);
}
ind = (ind - lastLen) % lastLen;
if (ind == 0) {
return "" + map.get(lastLen);
}
isFirst = false;
}
}
}
