Google 电面

先问了一个project就做题了~~
就一道题：decompression string

input ： abbaba4x[a]bb3x[abaa2x[bab]]
output : ab

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

e/smiley/QQ/em34.gif" smilieid="112" border="0" alt="" />

1.        
   
2. public String decompressString(String s) {
   
3.                 StringBuilder res = new StringBuilder();
   
4.                 StringBuilder current = new StringBuilder();
   
5.                 int i = 0;
   
6.                 Stack<Integer> vals = new Stack<>();
   
7.                 Stack<StringBuilder> strs = new Stack<>();
   
8.                 while(i < s.length()){
   
9.                         char c = s.charAt(i);
   
10.                         if(c >= 'a' && c <= 'z'){
    
11.                                 current.append(c);
    
12.                         } else if (c >= '0' && c <= '9'){
    
13.                                 int val = 0;
    
14.                                 while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
    
15.                                         val = val * 10 + s.charAt(i) - '0';
    
16.                                         i++;
    
17.                                 }
    
18.                                 i++;
    
19.                                 vals.push(val);
    
20.                                 continue;
    
21.                         } else if (c == '['){
    
22.                                 strs.push(current);
    
23.                                 current =  new StringBuilder();
    
24.                         } else if (c == ']'){
    
25.                                 int repeat = vals.pop();
    
26.                                 String str = current.toString();
    
27.                                 for(int j = 0; j < repeat - 1; j++){
    
28.                                         current.append(str);
    
29.                                 }
    
30.                                 if(strs.isEmpty() == false){
    
31.                                         strs.peek().append(current);
    
32.                                 } else {
    
33.                                         strs.push(current);
    
34.                                 }
    
35.                         }
    
36.                         i++;
    
37.                 }
    
38.                 return res.toString();
    
39.         }

复制代码

我也写了下

思路没错，撸出来了，欢迎改进意见

1. public String decompressString(String s) {
   
2.         Stack<String> stack = new Stack<String>();
   
3.         StringBuilder result = new StringBuilder();
   
4.         StringBuilder nested = new StringBuilder();
   
5.         for (int i = 0; i < s.length(); i++) {
   
6.                 char c = s.charAt(i);
   
7.                 if (c >= '0' && c <= '9') {
   
8.                         String pattern = s.substring(i, i + 2);
   
9.                         i += 3;
   
10.                         while (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
    
11.                                 pattern += s.charAt(i);
    
12.                                 i++;
    
13.                         }
    
14.                         i--;
    
15.                         stack.push(pattern);
    
16.                 } else if (c == ']') {
    
17.                         String[] pop = stack.pop().split("x");
    
18.                         String pattern = "";
    
19.                         for (int j = 0; j < Integer.parseInt(pop[0]); j++) {
    
20.                                 pattern += pop[1] + nested.toString();
    
21.                         }
    
22.                         nested.setLength(0);
    
23.                         nested.append(pattern);
    
24.                         if (stack.empty()) {
    
25.                                 result.append(nested.toString());
    
26.                                 nested.setLength(0);
    
27.                         }
    
28.                 } else {
    
29.                         result.append(c);
    
30.                 }
    
31.         }
    
32.         return result.toString();
    
33. }

复制代码

补充内容 (2016-5-22 10:19):
assume string里面只有小写字母，只用了楼主一个test case来validate

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

恭喜楼主，希望你顺利拿下onsite。 这已经是这个月内我看到的第3次考到压缩的题目了，简直超过了longest consecutive path成为第一高频了。

DaveLiu 发表于 2016-5-22 10:17
思路没错，撸出来了，欢迎改进意见

要是次数不止一位数你这样截取就不行了吧？

jy_121 发表于 2016-5-22 10:50
要是次数不止一位数你这样截取就不行了吧？

是的，当时也考虑到了，但是除了用regex，不知道有更好的方法不？

DaveLiu 发表于 2016-5-22 11:49
是的，当时也考虑到了，但是除了用regex，不知道有更好的方法不？

就是截取的时候一直截到x呢，比如用index of 找到离当前最近的x的下标

恭喜lz！ 要是截取的string里面本来就有xxx这种情况就不好这么做了吧

sal12 发表于 2016-6-8 07:53
我也写了下

我觉得把vals和strs合并成一个新object的话其实会更清晰：）

有人是用递归做的么