首页 > 代码库 > LeetCode 604. Design Compressed String Iterator (设计压缩字符迭代器)
LeetCode 604. 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 ‘ ‘
题目标签:Design
Java Solution:
Runtime beats 86.01%
完成日期:07/10/2017
关键词:Design
关键点:用两个list和一个cursor来找到char和对应char的count
1 public class StringIterator 2 { 3 ArrayList<Integer> counts; 4 ArrayList<Character> letters; 5 int cursor_index = 0; 6 7 public StringIterator(String compressedString) 8 { 9 counts = new ArrayList<>(); 10 letters = new ArrayList<>(); 11 12 for(int i=0; i<compressedString.length(); i++) 13 { 14 // if find a letter 15 if(Character.isLetter(compressedString.charAt(i))) 16 letters.add(compressedString.charAt(i)); 17 18 // if find a digit 19 else if(Character.isDigit(compressedString.charAt(i))) 20 { 21 int end = i+1; 22 // find the next non-digit char within the length 23 while(end < compressedString.length() && 24 Character.isDigit(compressedString.charAt(end))) 25 end++; 26 27 counts.add(Integer.parseInt(compressedString.substring(i, end))); 28 29 i = end - 1; 30 } 31 } 32 } 33 34 public char next() 35 { 36 char c; 37 38 // meaning string is finished 39 if(!hasNext()) 40 return ‘ ‘; 41 42 c = letters.get(cursor_index); 43 counts.set(cursor_index, counts.get(cursor_index) - 1); 44 45 if(counts.get(cursor_index) == 0) 46 cursor_index++; 47 48 49 return c; 50 } 51 52 public boolean hasNext() 53 { 54 // if string is finished 55 if(cursor_index > counts.size() - 1 ) 56 return false; 57 else // if string is not finished 58 return true; 59 } 60 } 61 62 /** 63 * Your StringIterator object will be instantiated and called as such: 64 * StringIterator obj = new StringIterator(compressedString); 65 * char param_1 = obj.next(); 66 * boolean param_2 = obj.hasNext(); 67 */
参考资料:N/A
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 604. Design Compressed String Iterator (设计压缩字符迭代器)