Leetcode - Design Compressed String Iterator

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 ' '

type StringIterator struct {
    str string
    idx int
    length int
    ranges []IdxRange
}

type IdxRange struct {
    start int
    end int
    val byte
}

func Constructor(com string) StringIterator {
    left := 0
    right := left + 1
    length := 0
    ranges := []IdxRange{}
    for right < len(com) {
        right = left + 1
        for right < len(com) && com[right] >= '0' && com[right] <= '9' {
            right++
        }
        if right >= len(com) {
            break
        }
        count := getCount(com, left+1, right)
        ranges = append(ranges, IdxRange{start: length, end: length+count-1, val: com[left]})
        length += count
        left = right
    }
    count := getCount(com, left+1, right)
    ranges = append(ranges, IdxRange{
        start: length,
        end: length+count-1,
        val: com[left],
    })
    length += count
    return StringIterator {
        str: com,
        length: length,
        ranges: ranges,
    }
}

func getCount(str string, start, end int) int {
    num, _ := strconv.Atoi(str[start:end])
    return num
}


func (this *StringIterator) Next() byte {
    if this.idx >= this.length {
        return ' '
    }
    idx := this.idx
    this.idx++
    i := 0
    for i = 0; i < len(this.ranges); i++ {
        if this.ranges[i].start <= idx && this.ranges[i].end >= idx {
            break
        }
    }
    return this.ranges[i].val
}


func (this *StringIterator) HasNext() bool {
    return this.idx < this.length
}


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

• 相关文章
• 全局相关文章