Java O(1) additional space solution. Easy to understand


  • 0
    E
    public class StringIterator {
        private final String str;
        private char curChar;
        private int curCharCount;
        private int nextId;
        
        public StringIterator(String compressedString) {
            this.str = compressedString;
            nextId = 0;
            moveToNextAvailable();
        }
        
        private void moveToNextAvailable() {
            for (; curCharCount == 0 && nextId < str.length();) {
                curChar = str.charAt(nextId++);
                for(; nextId < str.length() && Character.isDigit(str.charAt(nextId)); nextId++) {
                    int d = str.charAt(nextId) - '0';
                    curCharCount = 10 * curCharCount + d;
                }
            }
        }
        
        public char next() {
            if (!hasNext()) {
                return ' ';
            }
            char ret = curChar;
            curCharCount--;
            if (curCharCount == 0) {
                moveToNextAvailable();
            }
            return ret;
        }
        
        public boolean hasNext() {
            return curCharCount > 0;
        }
    }
    

    curChar is the current char the iterator points to, and curCharCount is its count. next() will always return curChar and decrease curCharCount. If all of curChar has been iterated, call moveToNextAvailable() to read the next char and its count, and update curChar and curCharCount accordingly.

    I saw some solutions copy the string data into a field of the StringIterator, which does not take O(1) space. Ideally an iterator should always take O(1) space in addition to the input data.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.