有效地在重复的子串由整数形成的字符串中查找字符

Question

给定一个String s和整数k。在具有以下规则的s形成的新字符串中查找第k个（0索引）字符的最节省空间的方法是什么（演示为示例）：

在从左到右迭代s中的每个char时，只要遇到整数（保证在2到9之间），就会用该整数重复到该点的子串。

ex）（s ='a2'，k = 1）：从s - >'aa'，返回'a'，因为它在新形成的字符串中处于索引1

ex）（s ='a2b3'，k = 2）：从s - >'aabaabaab'，返回'b'

显然，天真的解决方案是首先生成新的字符串并将其编入索引。但是，考虑到有大量数字并且字符串达到巨大尺寸的情况，肯定必须有更好的解决方案才能返回第k个字符。我一直在努力解决这个问题太久了，任何帮助都会受到赞赏！

Answer 1

如果你知道一些字符串s是另一个字符串t重复n次，那么字符串k中的索引s的字符等于字符串k2 = k mod t.length中具有索引t的字符。我们可以用它来解决这个任务：

1. 确定结果字符串的长度：

   len = 0
   for each character ch in s
       if ch is digit
           len = len * digit
       else
           len = len + 1

2. 通过字符串以相反的顺序迭代

    reverseS = reverse(s)
    curLen = len
    for each character ch in reverseS
        if ch is digit
            curLen = curLen / digit
            k = k mod curLen 
        else 
            if k == (curLen-1) then return ch as answer
            curLen = curLen - 1

因此，您根本不需要额外的内存（实际上是O(1)），算法具有O(n)时间复杂度，其中n是输入字符串的大小。

示例C ++代码：https://ideone.com/l8JxdQ

Answer 2

我能想到的最好的事情是只生成部分字符串。给定一个子字符串并重复它的次数，你当然可以使用modulo并确定你将在子字符串中的位置。这里的问题是，当您看到一个数字时，您将重复整个子字符串，包括任何先前的子字符串重复。

基本上，我不能想到一种数学方法来做到这一点，我认为你总是需要生成字符串直到迭代之前导致s.length() > k，或输入字符串中的最后一位数，以先到者为准。然后你可以k%s.length()找到正确的角色。

在C ++中看起来像这样：

char getK(string s, int k){
  string genString = "";
  string tempString = "";
  string digits = "0123456789";
  char c = '\0';
  const char * cc = &c;
  for (int i = 0; i < s.length(); i++){
    c = s[i];
    if (digits.find(c) != std::string::npos ){ // Digit
      if (i == s.length()-1 || k < genString.length()*atoi(cc)){ // Final digit or the next substring will contain genString[k]
        return genString[k%genString.length()]; // Modulo to find character location
      }
      tempString = genString;
      genString = "";
      for (int i = 0; i < atoi(cc); i++){
        genString += tempString;
      }
    } else { // Not a digit
      genString += c;
    }
    if (genString.length() > k) return genString[k]; // genString contains genString[k]
  }

  return genString[k]; // Silence compiler warnings
}

并且可以像这样使用：

int main()
{
  string s = "a2b3c7g3g8r4w5rf5";
  for (int k = 0; k < 20; k++){
    cout << i << ": " << getK(s, k) << endl;
  }
}

如果你在循环中放入一些cout语句，你会发现它只生成所需的字符串。