問題描述
Given 2 strings A and B, generate all possible solutions when B is merged with A.
Example: A = "hey", B = "sam"
out: heysam, hseaym, hesaym, sahemy etc. Notice order.
給出兩個字符串A和B，要求在不打亂A和B各自的順序下，返回A和B融合的所有可能結(jié)果犹撒。也就是說洋只，融合的結(jié)果忽略A的字符掺喻，B仍然是原來的順序，對A亦然兜挨。
詢問補(bǔ)充
對于產(chǎn)生的重復(fù)結(jié)果如何處理箩艺？假設(shè)接受重復(fù)結(jié)果。
結(jié)果對順序有沒有要求荤胁？假設(shè)沒有铜邮。
思路分析
這個題的思路應(yīng)該比較容易想出來，至少不會一上來想暴力破解寨蹋。
實(shí)在要暴力破解松蒜，那就要把A和B全部混在一起打亂，然后全排列已旧，然后一個個判斷是不是遵循A和B原來的順序秸苗。說實(shí)話實(shí)現(xiàn)起來還有點(diǎn)麻煩。
其實(shí)很明顯的一個方法就是遞歸运褪。反正每次從A或者B取一個字符惊楼，添加到結(jié)果集里面之后再遞歸下一層即可。
例如秸讹，對A="hey"第一次選'h'檀咙，B="sam"，其結(jié)果集就是A="ey"B="sam"的結(jié)果集所有字符串前面附加上一個'h'璃诀。
代碼
class Solution:
def merge(self, A, B):
if not A or not B:
return [A or B]
ret = []
for s in self.merge(A[1:], B):
ret.append(A[0] + s)
for s in self.merge(A, B[1:]):
ret.append(B[0] + s)
return ret
公式：T(m,n) = T(m-1,n)+T(m,n-1)=C（n,m+n）=(m+n)!/(m!*n!)弧可，聯(lián)想從[0,0]到[m,n]矩陣的走法。
總結(jié)
題目難度easy-medium劣欢，但是復(fù)雜度可能不是很容易計(jì)算棕诵。
