Google电面跪经

前些天面的狗家, 面试官迟到了5分钟，听口音判断不出来是哪里的人，说话慢吞吞有些结巴，全程比较严肃，不怎么和我交流，果不其然的跪了。

问题是这样的：

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

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

因为自己水平不够，这道题的确不太会写，跪也是正常的。还是乖乖刷题去了……

如果大家觉得有用的话，希望能给我加一下米，大米真的太少了。谢谢！

这个题别扭的地方在于大括号内部和外部结构不一样，所以最好是写两个函数互相递归调用，第一个递归函数线性扫描，第二个递归函数把大括号内的字符串按照','分割，然后对每个substring调用第一个递归函数，大概写了一下应该是没问题的

那ab[cd[ef]gh]ij返回什么？

SQLite 发表于 2019/01/20 02:04:53
那ab[cd[ef]gh]ij返回什么？

只有最内层是选一个么？

SQLite 发表于 2019-1-20 02:12
只有最内层是选一个么？

应该每层都是要选的，不是只有最内层选一个。{}就代表了从{}里选一个。

那有没有可能出现ab{c,{d,e},f}g
这种应该返回什么？按照我的理解是不是abcg, abdg, abeg, abfg？

好久没写python。。。。

首先greedy match最长的{}里的内容然后unzip和concat。。。

1. 
   
2. def unzip(strs):
   
3.     strs = strs.strip('{').strip('}')
   
4.     p = re.compile(r'\{([a-z],*)+\}')
   
5.     m = re.match(p, strs)
   
6.     if not m:  return [strs.split(',')]
   
7.     groups = unzip(m.group(0))
   
8.     return [''.join(strs[:m.start], g, strs[m.end():]) for g in groups]
   

复制代码

补充内容 (2019-1-20 17:15):
{a,b}{c,d}还有{a,b},{c,d}这样的貌似就不管用了.....好吧

a{a{b,d}f}g

->展开 {a{b,d}f}
->展开 a{b,d}f
->展开 {b,d}
    -> 返回 [b, d]
->返回[abf, adf]

->返回aabfg, aadfg

看逻辑stack好像也能做- - 然而很麻烦的样子