Skip to content

880. Decoded String at Index 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  string decodeAtIndex(string s, int k) {
    long size = 0;  // the length of the decoded `s`

    for (const char c : s)
      if (isdigit(c))
        size *= c - '0';
      else
        ++size;

    for (int i = s.length() - 1; i >= 0; --i) {
      k %= size;
      if (k == 0 && isalpha(s[i]))
        return string(1, s[i]);
      if (isdigit(s[i]))
        size /= s[i] - '0';
      else
        --size;
    }

    throw;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public String decodeAtIndex(String s, int k) {
    long size = 0; // the length of the decoded `s`

    for (final char c : s.toCharArray())
      if (Character.isDigit(c))
        size *= c - '0';
      else
        ++size;

    for (int i = s.length() - 1; i >= 0; --i) {
      k %= size;
      if (k == 0 && Character.isAlphabetic(s.charAt(i)))
        return s.substring(i, i + 1);
      if (Character.isDigit(s.charAt(i)))
        size /= s.charAt(i) - '0';
      else
        --size;
    }

    throw new IllegalArgumentException();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def decodeAtIndex(self, s: str, k: int) -> str:
    size = 0

    for c in s:
      if c.isdigit():
        size *= int(c)
      else:
        size += 1

    for c in reversed(s):
      k %= size
      if k == 0 and c.isalpha():
        return c
      if c.isdigit():
        size //= int(c)
      else:
        size -= 1