逆向工作法：

  • 逆向工作法，就是逆向思维，通过将问题反向思考求解。
  • 逆向工作法用到了栈的思想，但不需要栈也能实现。

例题：

给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

  • 如果所读的字符是字母，则将该字母写在磁带上。
  • 如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。 现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。
示例 1：
  1. 输入：S = "leet2code3", K = 10
  2. 输出："o"
  3. 解释：
  4. 解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
  5. 字符串中的第 10 个字母是 "o"。
示例 2：
  1. 输入：S = "ha22", K = 5
  2. 输出："h"
  3. 解释：
  4. 解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
示例 3：
  1. 输入：S = "a2345678999999999999999", K = 1
  2. 输出："a"
  3. 解释：
  4. 解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。
  5.  
提示：
  1. 2 <= S.length <= 100
  2. S 只包含小写字母与数字 2 到 9 。
  3. S 以字母开头。
  4. 1 <= K <= 10^9
  5. 解码后的字符串保证少于 2^63 个字母。

来源：力扣（LeetCode）第880题

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

解析：

首先先把题目要求的总长度算出来，这个比较容易，难点在于如何将第K个数从总长度中找出来。因为我们无法将整个数组都写出来，比如实例3，a的个数太多了，会导致内存不够的。所以我们只能找一种办法，在不用写出全部数组的情况下将第K个元素算出来。

如果每次都从前面思考，你会发现自己陷入瓶颈，找不到合适的方法满足要求。

可是如果反过来思考一下。我们刚才算出总长度用的方法是遍历数组，遇到字母+1，遇到数字就乘以这个数字。现在我们反过来思考，我们从后往前遍历，总长度遇到字母-1，遇到数字就除以这个数字。

假设我们遇到数字3，说明剩下的数字的总长度一定能正好分成3份，如果总长度是36，那么也就是说只有12个不同的答案，因为每一份的字母都是一样的。此时总长度为12，因此我们将K % 总长度12 ，看一下这个值是否等于0。如果不等于0，并且不是数字，就-1，直到K % 总长度 == 0，那么遍历到这个位置的S[i]就是所要求的元素。

上代码看一下：

  • 先来一个不用栈实现的官方解法

    1. class Solution:
    2. def decodeAtIndex(self, S: str, K: int) -> str:
    3.     size = 0
    4.     for c in S:
    5.         if c.isdigit():
    6.             size *= int(c)
    7.         else:
    8.             size += 1
    10.     for c in reversed(S):
    11.         K %= size
    12.         if K == 0 and c.isalpha():
    13.             return c
    14.         if c.isdigit():
    15.             size /= int(c)
    16.         else:
    17.             size -= 1

  • 然后是使用栈实现的，其实是一样的，从后往前遍历就是在模拟出栈，不过不用真的出栈，节省了时间

    1. class Solution(object):
    2. def decodeAtIndex(self, S, K):
    3.     stack = []
    4.     add = 0
    5.     for i in range(len(S)):
    6.         if S[i].isdigit():
    7.             add *= int(S[i])
    8.         else:
    9.             add += 1
    10.         stack.append(S[i])
    11.     while stack:
    12.         K = K % add
    13.         if K == 0 and stack[-1].isalpha():
    14.             return stack[-1]
    15.             
    16.         if stack[-1].isdigit():
    17.             add = add // int(stack.pop())
    18.         else:
    19.             add -= 1
    20.             stack.pop()

复杂度分析：

  • 时间复杂度：O(N)，其中 N 是 S 的长度。
  • 空间复杂度：O(1)。

总结：

根据题目所给的条件，来反向推导题目，有可能获得意想不到的效果。