A、B和C。如果C包含且仅包含来自A和B的所有字符,而且在C中属于A的字符之间保持原来在A中的顺序,属于B的字符之间保持原来在B中的顺序,那么称C是A和B的混编。实现一个函数,判断C是否是A和B的混编。
给定三个字符串A,B和C,及他们的长度。请返回一个bool值,代表C是否是A和B的混编。保证三个串的长度均小于等于100。
测试样例:
"ABC",3,"12C",3,"A12BCC",6
返回:true
A、B和C。如果C包含且仅包含来自A和B的所有字符,而且在C中属于A的字符之间保持原来在A中的顺序,属于B的字符之间保持原来在B中的顺序,那么称C是A和B的混编。实现一个函数,判断C是否是A和B的混编。
给定三个字符串A,B和C,及他们的长度。请返回一个bool值,代表C是否是A和B的混编。保证三个串的长度均小于等于100。
"ABC",3,"12C",3,"A12BCC",6
返回:true
# -*- coding:utf-8 -*- class Mixture: def chkMixture(self, A, n, B, m, C, v): while n!=0 and m!=0 and v!=0:#某一串已遍历完 a,b,c=A[0],B[0],C[0] if c==a and c==b:#A、B、C首字母相等 return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1) or self.chkMixture(A,n,B[1:],m-1,C[1:],v-1) elif c==a:#A、C首字母相等 return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1) elif c==b:#A、B首字母相等 return self.chkMixture(A,n,B[1:],m-1,C[1:],v-1) else: return False return True
python递归解法竟然也能通过。。
class Mixture:
def chkMixture(self, A, n, B, m, C, v):
# write code here
if not n+m==v:
return False
self.canForm=False
self.dfs(A,B,C)
return self.canForm
def dfs(self,s1,s2,s3):
if self.canForm:
return
if s3 == "":
self.canForm = True
return
if s1 and s1[0] == s3[0]:
self.dfs(s1[1:], s2, s3[1:])
if s2 and s2[0] == s3[0]:
self.dfs(s1, s2[1:], s3[1:])
未了方便处理,在A和B的前面添加一个空字符。dp的初始化如下图
下面就开始找dp的状态转移方程了
dp[i][j]就表示 A[0 ~ i-1]和B[0 ~ j-1]是否构成C[ 0 ~ i+j-1]
dp[i][j]=true的第二种情况是
dp绘制完成后,如下图所示
只要dp[n][m] = true,结果就是true
其中n为A字符串的长度,m为B字符串的长度。
整体代码如下
上的代码使用了额外的空间,时间复杂度为O(n^2)
虽然没有递归调用代码简洁,但是如果每个字符串的长度过长时,递归容易出现栈溢出。