LeetCode 604. Design Compressed String Iterator(java)


Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext.
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.
next() - if the original string still has uncompressed characters, return the next letter; Otherwise return a white space. hasNext() - Judge whether there is any letter needs to be uncompressed.
Note: Please remember to RESET your class variables declared in StringIterator, as static/class variables are persisted across multiple test cases. Please see here for more details.
Example:

StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");

iterator.next(); // return 'L'
iterator.next(); // return 'e'
iterator.next(); // return 'e'
iterator.next(); // return 't'
iterator.next(); // return 'C'
iterator.next(); // return 'o'
iterator.next(); // return 'd'
iterator.hasNext(); // return true
iterator.next(); // return 'e'
iterator.hasNext(); // return false
iterator.next(); // return ' '

考え方:まず、私が考えているのは、stackを1つ使って、後ろから前へ、最後に生成した文字をstackに詰め込み、next()とhasNext()のたびにstackからpopが出てくることです.しかし、この方法はleetcodeを越えられない.「a 1038373845 b 1032394854」という例が現れ、時間が非常に遅いので、左からpopごとに-1をカウントし、カウントが0になったら2番目の文字を開始する方法を変えた.以下は2つのメソッドのコードですが、2つ目のメソッドだけがLeetCodeを通過できます.
//   :stack
class StringIterator {

    Stack stack = new Stack<>();

    public StringIterator(String compressedString) {
        int count = 1, num = 0, len = compressedString.length();
        for (int i = len - 1; i >= 0; i--) {
            char c = compressedString.charAt(i);
            if (Character.isDigit(c)) {
                int end = i;
                while (i < len && Character.isDigit(compressedString.charAt(i))) {
                    i--;
                }
                i++;
                for (int j = i; j <= end; j++) {
                    num = num * 10 + compressedString.charAt(j) - '0';
                    if (num > Integer.MAX_VALUE) {
                        num = Integer.MAX_VALUE;

                    }
                }
                count = num;
                num = 0;
            } else {
                for (int j = 0; j < count; j++) {
                    stack.push(c);
                }
                count = 1;
            }
        }
    }

    public char next() {
        return stack.isEmpty() ? ' ' : stack.pop();
    }

    public boolean hasNext() {
        return stack.isEmpty() ? false : true;
    }
}
//   :
class StringIterator {
    char letter;
    int count;
    int index;
    int len;
    String s;
    public StringIterator(String compressedString) {
        s = compressedString;
        len = s.length();
        index = 0;
        helper();
    }

    public char next() {
        if (count > 0) {
            count--;
            return letter;
        } else {
            if (index == len) {
                return ' '; 
            } else {
                helper();
                count--;
                return letter;
            }
        }
    }

    public boolean hasNext() {
        return (index == len && count <= 0) ? false : true;
    }

    public void helper() {
        char c = s.charAt(index);
        letter = c;
        int num = 0;
        while (++index < len && Character.isDigit(s.charAt(index))) {
            num = num * 10 + s.charAt(index) - '0';
        }
        count = num;
    }
}