题目

• 概述：给定一个字符串，将其编码成另一个字符串，编码规则：字母不变，数字则将当前已经编码的字符串重复（数字大小-1）次。给定一个索引，输出编码后字符串对应索引的字符

• 输入：

  1. 字符串，长度范围[2, 100]，由字母开头，且仅由小写英文字母和数字2~9组成
  2. 索引，大小范围[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;
        }
    }
}