请教一道string的题T_T

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

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

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

def parseStr(s):
        finalResult = ''
        result = ['']
        inBrace = False
        currentWord = ''
        currentQueue = []
        for i in s:
                if i is '{':
                        inBrace = True       
                elif i is '}':
                        inBrace = False
                        currentQueue.append(currentWord)
                        currentWord = ''       
                        result = [ a + b for b in currentQueue for a in result]
                        currentQueue = []
                elif i is ',' and inBrace:
                        currentQueue.append(currentWord)
                        currentWord = ''       
                elif i is ',':
                        result = [ a + i for a in result]
                        finalResult = finalResult+ ','.join(result)
                        result = ['']
                else:
                        if not inBrace:
                                result = [ a + i for a in result]
                        else:
                                currentWord += i       
        return finalResult+ ','.join(result)

print parseStr('a{1,2}b{2,3}c')
print parseStr('a{.py,.java}')
print parseStr('a.java,b.py,c{.java,.py}')
print parseStr('a.java,b.py,c{.java,.py},d{.java,.py}')

如果沒有nested braces的話, 可以直接用iteration做.

所有在{}裏面的東西可以split with ','
然後把它們放到list裏, 接著就把它們append to previous result 1 by 1.



补充内容 (2019-3-16 10:10):
求大米!!

支持嵌套的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,...

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随便写了一下，确实挺长。。求点米

KaWing 发表于 2019-3-16 10:10
def parseStr(s):
        finalResult = ''
        result = ['']

超级感谢！！先试着加个大米先

报告一下，print parseStr('a.java,c{.java,.py}'，b.py)中间会多个‘，’
我改了一下：
elif i is ',':
                        result = [ a + i for a in result]
                        finalResult = finalResult+ ''.join(result)
                        result = ['']

非常感谢啊 python真的挺方便

现在流行用Python刷题？

chore 发表于 2019-3-16 12:38
现在流行用Python刷题？

不建議在Algorithm比賽中用python, 但面試時用python通常會比較方便. 至少寫得比較少....

我就是用c++做的，代码最后写晕了
follow up确实还有nested {}。。。

1. def parse_string(string):
   
2.     def find_sub(s, i) -> List[str]:
   
3.         sub = ''
   
4.         while i < len(s) and '}' not in sub:
   
5.             sub += s[i]
   
6.             i += 1
   
7.         return sub[:-1].split(','), i - 1
   
8.     if not string: return []
   
9.     prefix, res = '', ['']
   
10.     index = 0
    
11.     while index < len(string):
    
12.         if string[index] == '{':
    
13.             sub, index = find_sub(string, index + 1)
    
14.             res = [i + j for i in res for j in sub]
    
15.         else:
    
16.             res = [i + string[index] for i in res]
    
17.         index += 1
    
18.     return res

复制代码

看在我半夜還在打code的份上, 給點米吧

补充内容 (2019-3-16 13:46):
string “a{1,2}b{3,4}d” 應該是输出 ["a1b3d","a2b3d","a1b4d","a2b4d"]?
a.java,b.py,c{.java,.py}, 它应该输出的是 ["a.java,b.py,c.java", "a.java,b.py,c.py"]?

imiochen24 发表于 2019-3-16 13:43
[mw_shl_code=python,true]def parse_string(string):
    def find_sub(s, i) -> List[str]:
        su ...

这是我的错，我在整理面经，两道相似的题，但不一样的output。发的时候以为是一样的。

谢谢指出。

chore 发表于 2019-3-16 12:38
现在流行用Python刷题？

onsite必备