Google电面跪经

感觉难点在于对于子问题的返回结果处理也有多重情况，a{b, c} -> ab  ac 而a,{b,c} -> a b c
再考虑多重嵌套的，就算是用递归需要处理的corner case也太多了点，强行凑出解得话很难bug free,只能看面试官认不认同你的思路了

mysteryjoe 发表于 2019-1-23 04:50
感觉难点在于对于子问题的返回结果处理也有多重情况，a{b, c} -> ab  ac 而a,{b,c} -> a b c
再考虑多重嵌 ...

求大神给个容易解释的solution

感觉可以建个trie，一套dfs下来就都出来了

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

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

写了个recursion，感觉时间和空间复杂度都很高，

1. import java.util.*;
   
2. public class Main{
   
3.         public List<String> parse(String s){
   
4.                 List<String> pre = new ArrayList<>();
   
5.                 List<String> ans = new ArrayList<>();
   
6.                 char[] arr = s.toCharArray();
   
7.                 pre.add("");
   
8.                 int i = 0;
   
9.                 int start = 0;
   
10.                 String cur = "";
    
11.                 while(i < arr.length){
    
12.                         if(arr[i] == ','){                            
    
13.                                 for(String str : pre){
    
14.                                         ans.add(cur);
    
15.                                         cur = "";
    
16.                                 }
    
17.                         }
    
18.                         else if(arr[i] == '{'){
    
19.                                 int cnt =1;
    
20.                                 start = i +1;                               
    
21.                                 while(i < arr.length && cnt != 0){
    
22.                     i++;
    
23.                                         if(arr[i] == '{') cnt++;
    
24.                                         else if(arr[i] == '}') cnt--;              
    
25.                                 }
    
26.                                 for(String str : parse(s.substring(start,i))){
    
27.                                         for(String preStr : pre){
    
28.                                                 ans.add(preStr + cur +str);
    
29.                                         }
    
30.                                 }
    
31.                                 cur = "";                               
    
32.                                 pre = ans;
    
33.                                 ans = new ArrayList<>();
    
34.                                                                
    
35.                         }else{
    
36.                                 cur += arr[i];                               
    
37.                         }
    
38.                         i++;
    
39.                         if(i == arr.length){
    
40.                             for(String str : pre){
    
41.                                 ans.add(str + cur);
    
42.                             }
    
43.                         }
    
44.                 }
    
45.                 return ans;
    
46.         }
    
47.         public static void main(String arg[]){
    
48.                 String s = "a{a{b,d}f}g{c,d}h";
    
49.                 Main sol = new Main();
    
50.                 System.out.println(sol.parse(s) );
    
51.         }
    
52. }

复制代码

不知道是多少，请大牛指导



补充内容 (2019-1-23 11:32):
不好意思，有bug，14 行应为 ans.add(str + cur);

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

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

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

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

2012ECE 发表于 2019-1-23 06:07
感觉可以建个trie，一套dfs下来就都出来了

没大明白