Question

604. Design Compressed String Iterator

中文文档

Description

Design and implement a data structure for a compressed string iterator. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

Implement the StringIterator class:

• next() Returns the next character if the original string still has uncompressed characters, otherwise returns a white space.
• hasNext() Returns true if there is any letter needs to be uncompressed in the original string, otherwise returns false.

 

Example 1:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

 

Constraints:

• 1 <= compressedString.length <= 1000
• compressedString consists of lower-case an upper-case English letters and digits.
• The number of a single character repetitions in compressedString is in the range [1, 10^9]
• At most 100 calls will be made to next and hasNext.

Solutions

Solution 1

class StringIterator:
  def __init__(self, compressedString: str):
    self.d = []
    self.p = 0
    n = len(compressedString)
    i = 0
    while i < n:
      c = compressedString[i]
      x = 0
      i += 1
      while i < n and compressedString[i].isdigit():
        x = x * 10 + int(compressedString[i])
        i += 1
      self.d.append([c, x])

  def next(self) -> str:
    if not self.hasNext():
      return ' '
    ans = self.d[self.p][0]
    self.d[self.p][1] -= 1
    if self.d[self.p][1] == 0:
      self.p += 1
    return ans

  def hasNext(self) -> bool:
    return self.p < len(self.d) and self.d[self.p][1] > 0


# Your StringIterator object will be instantiated and called as such:
# obj = StringIterator(compressedString)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class StringIterator {
  private List<Node> d = new ArrayList<>();
  private int p;

  public StringIterator(String compressedString) {
    int n = compressedString.length();
    int i = 0;
    while (i < n) {
      char c = compressedString.charAt(i);
      int x = 0;
      while (++i < n && Character.isDigit(compressedString.charAt(i))) {
        x = x * 10 + (compressedString.charAt(i) - '0');
      }
      d.add(new Node(c, x));
    }
  }

  public char next() {
    if (!hasNext()) {
      return ' ';
    }
    char ans = d.get(p).c;
    if (--d.get(p).x == 0) {
      ++p;
    }
    return ans;
  }

  public boolean hasNext() {
    return p < d.size() && d.get(p).x > 0;
  }
}

class Node {
  char c;
  int x;

  Node(char c, int x) {
    this.c = c;
    this.x = x;
  }
}

/**
 * Your StringIterator object will be instantiated and called as such:
 * StringIterator obj = new StringIterator(compressedString);
 * char param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

class StringIterator {
public:
  StringIterator(string compressedString) {
    int n = compressedString.size();
    int i = 0;
    while (i < n) {
      char c = compressedString[i];
      int x = 0;
      while (++i < n && isdigit(compressedString[i])) {
        x = x * 10 + (compressedString[i] - '0');
      }
      d.push_back({c, x});
    }
  }

  char next() {
    if (!hasNext()) return ' ';
    char ans = d[p].first;
    if (--d[p].second == 0) {
      ++p;
    }
    return ans;
  }

  bool hasNext() {
    return p < d.size() && d[p].second > 0;
  }

private:
  vector<pair<char, int>> d;
  int p = 0;
};

/**
 * Your StringIterator object will be instantiated and called as such:
 * StringIterator* obj = new StringIterator(compressedString);
 * char param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

type pair struct {
  c byte
  x int
}

type StringIterator struct {
  d []pair
  p int
}

func Constructor(compressedString string) StringIterator {
  n := len(compressedString)
  i := 0
  d := []pair{}
  for i < n {
    c := compressedString[i]
    x := 0
    i++
    for i < n && compressedString[i] >= '0' && compressedString[i] <= '9' {
      x = x*10 + int(compressedString[i]-'0')
      i++
    }
    d = append(d, pair{c, x})
  }
  return StringIterator{d, 0}
}

func (this *StringIterator) Next() byte {
  if !this.HasNext() {
    return ' '
  }
  ans := this.d[this.p].c
  this.d[this.p].x--
  if this.d[this.p].x == 0 {
    this.p++
  }
  return ans
}

func (this *StringIterator) HasNext() bool {
  return this.p < len(this.d) && this.d[this.p].x > 0
}

/**
 * Your StringIterator object will be instantiated and called as such:
 * obj := Constructor(compressedString);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */