No.0021-CareerCup

问题描述

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融合的所有可能结果。也就是说，融合的结果忽略A的字符，B仍然是原来的顺序，对A亦然。

询问补充

对于产生的重复结果如何处理？假设接受重复结果。
结果对顺序有没有要求？假设没有。

思路分析

这个题的思路应该比较容易想出来，至少不会一上来想暴力破解。
实在要暴力破解，那就要把A和B全部混在一起打乱，然后全排列，然后一个个判断是不是遵循A和B原来的顺序。说实话实现起来还有点麻烦。
其实很明显的一个方法就是递归。反正每次从A或者B取一个字符，添加到结果集里面之后再递归下一层即可。
例如，对A="hey"第一次选'h'，B="sam"，其结果集就是A="ey"B="sam"的结果集所有字符串前面附加上一个'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!)，联想从[0,0]到[m,n]矩阵的走法。

总结

题目难度easy-medium，但是复杂度可能不是很容易计算。