首页 > 代码库 > 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
  这道题目给了我们一个string, string是由一个char 紧接着 一个 正数int 这种重复排列。让我们设计一个迭代器,把每一个字母按照它后面那个数字来print出。
  StringIterator: 当我们创造一个 StringIterator object 的时候,我们要把 这个string 保存好,以便于之后可以call next 和 hasNext。
        我们可以建立两个list, counts 和 letters。 遍历compressedString, 判断这一个char 是不是 letter, 是的话,直接把char 存进letters list。如果这个char 是数字digit 的话,那么我们需要继续往后找,直到找到一个不是数字的char,或者它超出size了。
        因为数字可以是1位,也可以2位或者更多。
 
  Next():当我们存好了letters 和counts, 就利用counts 来return 相对应的char, 每次用完一个char, 要把它的count - 1。如果当这个count = 0 的时候,那么我们需要移动到下一个char。这里我们需要一个cursor_index 来跟踪我们的char。
 
  hasNext():这里只需要判断,如果我们的cursor_index 超出了 任意一个list 的size, 就表示已经用完了所有的char。
 
 

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 (设计压缩字符迭代器)