Back to Leetcode

Readme

Recursion/3614.Process-String-with-Special-Operations-II/Readme.md

latest1.3 KB
Original Source

3614.Process-String-with-Special-Operations-II

很显然,构造完全之后的字符串非常长,我们不可能在此基础上定位第k个元素。此题极大概率是递归反推。

我们分类思考每种操作下的第k个字符(注意是1-index)是什么情况:

  1. 添加一个字符,使得长度从a变成了a+1. 如果k=a+1,那么答案就是最新添加的字符。否则,递归求原字符串里的第k个。
  2. 删减最后一个字符,使得长度从a变成了a-1. 这种情况下k不可能是a(否则无解),因此等效于递归求原字符串里的第k个。
  3. 将字符串copy+append,使得长度从a变成了2a. 显然如果k<=a,递归求原字符串里的第k个。如果k>a,递归求原字符串里的第k-a个。
  4. 将字符串反转,长度依然是k。显然,递归求原字符串里的第a+1-k个。

综上,只要知道每个回合的操作和长度变化,我们就可以把“求当前字符串的第k个元素”,逆推为“求前一个回合字符串的第k'个元素”,其中k'的计算如上。

注意,这个题可能无解。逆推的前提是正向的变化合法存在。所以我们必须先正向走一遍,记录下每个回合的字符串长度,最后检查k是否在最终长度的范围内。