请教一道string的题T_T

给一个String “a{1,2}b{3,4}d”输出 a1b3d,a2b3d,a2b3d,a2b4d  这个输出例子不对，是a1b3d,a2b3d,a1b4d,a2b4d 还是 a1b3d,a1b4d,a2b3d,a2b4d？

1. public static void generate(String s){
   
2.         Deque<String> dq = new LinkedList<>();
   
3.         dq.add("");
   
4.         String cur = "";
   
5.         for(int i = 0; i < s.length(); i++){
   
6.             char c = s.charAt(i);
   
7.             if (c == '{') {
   
8.                 processQueue(dq, cur);
   
9.                 cur = "";
   
10.                 List<String> temp = brackets(s, i + 1);
    
11.                 i = Integer.parseInt(temp.get(temp.size() - 1)) - 1;
    
12.                 temp.remove(temp.size() - 1);
    
13.                 int size = dq.size();
    
14.                 while(size-- > 0){
    
15.                     String prefix = dq.pollFirst();
    
16.                     for(String tmp: temp){
    
17.                         dq.add(prefix + tmp);
    
18.                     }
    
19.                 }
    
20.             }else{
    
21.                 cur += c;
    
22.             }
    
23.         }
    
24.         if(cur != null){
    
25.             processQueue(dq, cur);
    
26.         }
    
27.         while (!dq.isEmpty()) {
    
28.             System.out.println(dq.poll());
    
29.         }
    
30.     }
    
31. 
    
32.     public static Deque<String> processQueue(Deque<String> dq, String toBeAdded){
    
33.         int size = dq.size();
    
34.         while(size-- > 0){
    
35.             dq.add(dq.pollFirst() + toBeAdded);
    
36.         }
    
37.         return dq;
    
38.     }
    
39.     public static List<String> brackets(String s, int start){
    
40.         List<String> res = new ArrayList<>();
    
41.         String cur = "";
    
42.         int left = 1;
    
43.         int i;
    
44.         for(i = start; i < s.length() && left > 0; i++){
    
45.             char c = s.charAt(i);
    
46.             if(c == ','){
    
47.                 res.add(cur);
    
48.                 cur = "";
    
49.             }else if(c == '{'){
    
50.                 List<String> temp = brackets(s, i + 1);
    
51.                 i = Integer.parseInt(temp.get(temp.size() - 1)) - 1;
    
52.                 temp.remove(temp.size() - 1);
    
53.                 res.addAll(temp);
    
54.             }else if(c == '}'){
    
55.                 left--;
    
56.                 if(cur.length() != 0){
    
57.                     res.add(cur);
    
58.                     cur = "";
    
59.                 }
    
60.             }else{
    
61.                 cur += c;
    
62.             }
    
63.         }
    
64.         res.add(String.valueOf(i));
    
65.         return res;
    
66.     }

复制代码

补充内容 (2019-3-17 06:38):
java随便写了一下，确实挺长。。求点米

zdj0712 发表于 2019-3-16 13:51
这是我的错，我在整理面经，两道相似的题，但不一样的output。发的时候以为是一样的。

谢谢指出。

可以说一下面经完整题目是啥

就是第一个例子是一个面经。输入输出都给了，顺序无所谓。
后面的例子是一个面经，让implement shell中{}的功能。后面的follow up是如果有nested{}怎么做。

请问这题nested有没有人做出来的？写了半天写不出来。。。

支持嵌套的Java版本
维护一个list记录已有的options, 比如a{1,2} 处理完的时候list是[a1,a2]
每次遇到bracket时候 recursive call 返回新的list, 两个list合并后size是a*b
最后join list ","

写完感觉代码可读性一般，求建议
顺便求大米

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. public class ParseString{
   
5.         public static void main(String[] args){
   
6.                 ParseString solution = new ParseString();
   
7.                 System.out.println("Input:" + "a{1,2}b{3,4}c{5,6}" +  " Result:" + solution.parseString("a{1,2}b{3,4}c{5,6}"));
   
8.                 System.out.println("Input:" + "{a,b}.txt" +  " Result:" + solution.parseString("{a,b}.txt"));
   
9.                 System.out.println("Input:" + "a.java,b.py,c{.java,.py}" +  " Result:" + solution.parseString("a.java,b.py,c{.java,.py}"));
   
10.                 System.out.println("Input:" + "a{1,2}b{d{7,8},4}c{5,6}" +  " Result:" + solution.parseString("a{1,2}b{d{7,8},4}c{5,6}"));
    
11.         }
    
12.        
    
13.         public String parseString(String str){
    
14.                 Queue<Character> queue = new LinkedList<>();
    
15.                 for(char c: str.toCharArray()){
    
16.                         queue.offer(c);
    
17.                 }
    
18.                 List<String> res = parseBracket(queue);
    
19.                 return String.join(",", res);
    
20.         }
    
21.        
    
22.         public List<String> parseBracket(Queue<Character> queue){
    
23.                 List<String> res = new ArrayList<>();
    
24.                 StringBuilder sb = new StringBuilder();
    
25.                 List<String> currentOptions = new ArrayList<>();
    
26.                 currentOptions.add("");
    
27.                 while(!queue.isEmpty()){
    
28.                         Character c = queue.poll();
    
29.                         if(c.equals('{')){
    
30.                                 String currentString = sb.toString();
    
31.                                 sb = new StringBuilder();
    
32.                                 List<String> nextOptions = parseBracket(queue); // Recursive
    
33.                                 List<String> next = new ArrayList<>();
    
34.                                 for(String previous : currentOptions){
    
35.                                         for(String option : nextOptions){
    
36.                                                 next.add(previous + currentString + option);
    
37.                                         }
    
38.                                 }
    
39.                                 currentOptions = next;
    
40.                         }else if(c.equals('}') || c.equals(',')){
    
41.                                 res.add(finishCurrentOption(sb, currentOptions));
    
42.                                 sb = new StringBuilder();
    
43.                                 currentOptions = new ArrayList<>();
    
44.                                 currentOptions.add("");
    
45.                                 if(c.equals('}')) return res;
    
46.                         }else{
    
47.                                 sb.append(c);
    
48.                         }
    
49.                 }
    
50.                 res.add(finishCurrentOption(sb, currentOptions));
    
51.                 return res;
    
52.         }
    
53.        
    
54.         private String finishCurrentOption(StringBuilder sb, List<String> currentOptions){
    
55.                 String currentString = sb.toString();
    
56.                 sb = new StringBuilder();
    
57.                 for(int i=0; i<currentOptions.size(); i++){
    
58.                         sb.append(currentOptions.get(i));
    
59.                         sb.append(currentString);
    
60.                         if(i != currentOptions.size()-1) sb.append(',');
    
61.                 }
    
62.                 return sb.toString();
    
63.         }
    
64. }

复制代码

补充内容 (2019-4-14 04:40):
log:
Input:{a,b}.txt Result:a.txt,b.txt
Input:a.java,b.py,c{.java,.py} Result:a.java,b.py,c.java,c.py
Input:a{1,2}b{d{7,8},4}c{5,6} Result:a1bd7,d8c5,a1bd7,d8c6,a1b4c5,a1b4c6,a2bd7,d8c5,a2bd7,d8c6,...