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 ' '
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | 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(); */ |
评论 (0)
