Java solution with time = O(1), space = O(1) with detailed explanation


  • 0
    M

    Idea:
    Maintain a original string,
    an index to denote which letters;
    a count to denote its corresponding count;
    a nextCharIndex to denote the position of next letter, since the count may be > 10, so we need to save the next char index;

    initialize(): index to 0; count is its corresponding number;
    next(): check whether it hasNext first; then count--; return s.charAt(index);
    hasNext(): if count > 0, return true;
    if count == 0, find the next letter; if no letters, return false; otherwise, get the count by calculating the following number;

    Time = O(1),
    Space = O(1).

    public class StringIterator {
        String s = null;
        int index = 0;
        int count = 0;
        int nextCharIndex = 0;
    
        public StringIterator(String compressedString) {
            // assumption: compressedString is not null and empty;
            // it must be exactly the form: letter + number;
            this.s = compressedString;
            this.index = 0;
            int tmp = 1;
            while (tmp < s.length() && s.charAt(tmp) >= '0'
                    && s.charAt(tmp) <= '9') {
                this.count = this.count * 10 + s.charAt(tmp) - '0';
                tmp++;
            }
            this.nextCharIndex = tmp;
        }
    
        public char next() {
            if (!hasNext()) {
                return ' ';
            }
            count--;
            return s.charAt(index);
        }
    
        public boolean hasNext() {
            if (count > 0) {
                return true;
            } else {
                index = nextCharIndex;
                if (index >= s.length()) {
                    return false;
                }
                count = 0;
                int tmp = index + 1;
                while (tmp < s.length() && s.charAt(tmp) >= '0'
                        && s.charAt(tmp) <= '9') {
                    count = count * 10 + s.charAt(tmp) - '0';
                    tmp++;
                }
                nextCharIndex = tmp;
            }
            return true;
        }
    
    }
    

Log in to reply
 

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