一道google onsite题目

xiyan

给一个List<List<Character>>,打印出所有组合
eg.
% ]- ?4 n3 ]# H$ I; }( [( }{
0 X+ ]% S7 N5 p7 I    {a, b},
( J0 Q. o% I, ]$ F9 F    {c, d, e},
    {f, g}
}
6 {- G+ `! k4 K# h" H  k* B3 t
* g$ E" Q% ^- j( d打印出来：
{a, c, f}
- d" G6 ^0 B) |8 A/ n{a, c, g}
* `+ O& h! o! z" a{a, d, f}
{a, d, g}
{a, e, f}
{a, e, g}
{b, c, f}
* x. W6 o. |9 m  s......
# a$ d4 f' `3 C5 |7 u& ?
很容易想到的解法是
/ g8 q9 R4 s7 a6 n$ v) D1 ]2 f& ^先计算前两个list的组合{a, c} {a, d} {a, e} {b, c} {b, d} {b, e}，得到结果再与第三个list计算，最后打印出来，但这样需要额外的空间保存中间结果，类似树的level traverse
怎么优化空间复杂度，不需要维护中间结果
- @5 O% O4 D  d* R' t
  C" M0 b' F/ x; M

dayouxia

lc原题，letter combinations of a phone number.

cpcs

不可能不需要吧。。。dfs

liuzhe1218

直接一个dfs就可以搞出来了啊。。。