[数据结构与算法]LeetCode 880 Decoded String at Index (递归，推荐)

You are given an encoded string?s. To decode the 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?d, the entire current tape is repeatedly written?d - 1?more times in total.

Given an integer?k, return?the?kth?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".

Constraints:

• 2 <= s.length <= 100
• s?consists of lowercase English letters and digits?2?through?9.
• s?starts with a letter.
• 1 <= k <= 109
• It is guaranteed that?k?is less than or equal to the length of the decoded string.
• The decoded string is guaranteed to have less than?263?letters.

题目链接：https://leetcode.com/problems/decoded-string-at-index/

题目大意：给一个由小写字母a-z和数字2-9组成的字符串，遇到一个字母就打出，遇到一个数字就将当前字符串重复数字减1次，求按照这种规则生成的字符串的第k位

题目分析：按照题目要求的规则累计当前字符串长度，在遇到数字时，判断答案是否在以当前数字为周期的字符串中，如果在则缩小查询范围即可

2ms，时间击败45%

class Solution {

    public String dfs(String s, int n, long k) {
        long strLen = 0;
        if (k == 0) {
            return s.charAt(0) + "";
        }
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) <= 'z' && s.charAt(i) >= 'a') {
                strLen++;
                if (strLen == k) {
                    return s.charAt(i) + "";
                }
            } else {
                long num = s.charAt(i) - '0';
                for (long j = 2; j <= num; j++) {
                    if (strLen * j >= k) {
                        // System.out.println("i = " + i + " k = " + (k - strLen * (j - 1)));
                        return dfs(s, i, k - strLen * (j - 1));
                    }
                }
                strLen = strLen * num;
            }
        }
        return "";
    }
    
    public String decodeAtIndex(String s, int k) {
        return dfs(s, s.length(), (long)k);
    }
}