Google – Run Length Encoding Iterator

Google – Run Length Encoding Iterator
Run length encoding就是比如aaaabbccc压缩成4a2b3c
题目给一个encoding好的string, 比如4a2b3c，要求写一个iterator来遍历原来的string.
[Solution]
除了iterator一般的edge case以外，这道题还需要注意一些其他的edge case，比如0a2b3c，4a0b3c
Idea就是用一个start pointer指向下一个数字，无论下一个是不是0. 如果当前的cnt用完之后，就从start开始往后找下一个不为0的数字。

class EncodingIterator implements Iterator<Character> {

 

  String s;

  int cnt;

  Character c;

  int start;

 

  public EncodingIterator(String s) {

    if (s == null || s.isEmpty()) {

      return;

    }

    this.s = s;

    while (cnt == 0) {

      int i = start;

      for (; i < s.length(); i++) {

        if (!Character.isDigit(s.charAt(i))) {

          break;

        }

      }

      if (i == s.length()) {

        return;

      }

      else {

        this.cnt = Integer.parseInt(s.substring(start, i));

        this.c = s.charAt(i);

        start = i + 1;

      }

    }

  }

 

  @Override

  public boolean hasNext() {

    return c != null;

  }

 

  @Override

  public Character next() {

    if (c == null) {

      return null;

    }

    Character result = c;

    this.cnt--;

    while (cnt == 0) {

      c = null;

      int i = start;

      for (; i < s.length(); i++) {

        if (!Character.isDigit(s.charAt(i))) {

          break;

        }

      }

      if (i == s.length()) {

        break;

      }

      else {

        this.cnt = Integer.parseInt(s.substring(start, i));

        this.c = s.charAt(i);

        start = i + 1;

      }

    }

    return result;

  }

}

Read full article from Google – Run Length Encoding Iterator