字符串交错组成

[编程题]字符串交错组成

热度指数：5937 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于三个字符串A，B，C。我们称C由A和B交错组成当且仅当C包含且仅包含A，B中所有字符，且对应的顺序不改变。请编写一个高效算法，判断C串是否由A和B交错组成。

给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否由A和B交错组成。保证三个串的长度均小于等于100。

测试样例：

"ABC",3,"12C",3,"A12BCC",6

返回：true

算法知识视频讲解

Python

雷凌云

python 递归解法

# -*- coding:utf-8 -*-
class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        if self.check(A, B, C):
            return True
        return False
    def check(self, A, B, C):
        if A == C or B == C:
            return True
        if A[0] == C[0] and self.check(A[1:], B, C[1:]):
            return True
        if B[0] == C[0] and self.check(A, B[1:], C[1:]):
            return True
        return False

发表于 2019-08-10 22:36:21 回复(0)

Python

gallo

我可能是走捷径了吧可能不是这道题要考的寓意但是我想说python大法好没有看懂大家的动态规划啥的但是我的只是字符串的比较。两个字符串排序后看是否相等相等就True

class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        # write code here
        if n+m<=100 and v<=100:
            d = list(A+B)
            d.sort()
            e = list(C)
            e.sort()
            if d == e:
                return True

发表于 2019-01-19 20:27:09 回复(0)

Python

离疏

# -*- coding:utf-8 -*-
class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        if n == 0 or m == 0 or v == 0:#ABC中任何一个已遍历完毕，则为True
            return True
        if A[0] == C[0] and B[0] != C[0]:#C中当前首字符为A的首字符
            return self.chkMixture(A[1:], n-1, B, m, C[1:], v-1)
        if B[0] == C[0] and A[0] != C[0]:#C中当前首字符为B的首字符
            return self.chkMixture(A, n, B[1:], m-1, C[1:], v-1)
        if A[0] == C[0] == B[0]:#C中当前首字符可能为A的首字符，也可能为B的首字符
            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)

发表于 2018-08-30 11:41:20 回复(0)

Python

改个名字解解毒...

#递归版本
if n == 0 or m == 0 or v == 0:
            return True
        if A[0] == C[0] and B[0] != C[0]:
            return self.chkMixture(A[1:], n-1, B, m, C[1:], v-1)
        if B[0] == C[0] and A[0] != C[0]:
            return self.chkMixture(A, n, B[1:], m-1, C[1:], v-1)
        if A[0] == C[0] == B[0]:
            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)

        return False
#动态规划版本  class Mixture:
    def chkMixture(self, A, n, B, m, C, v):
        # write code here
        dp = [[False for i in range(m+1)] for j in range(n+1)]
        
        for i in range(n+1):
            for j in range(m+1):
                if i == j == 0:
                    dp[i][j] = True
                elif i == 0 and j != 0:
                    dp[i][j] = dp[i][j-1] and B[j-1] == C[j-1]
                elif i != 0 and j == 0:
                    dp[i][j] = dp[i-1][j] and A[i-1] == C[i-1]
                elif A[i-1] == C[i+j-1] and dp[i-1][j] == True:
                    dp[i][j] = True
                elif B[j-1] == C[i+j-1] and dp[i][j-1] == True:
                    dp[i][j] = True
        return dp[-1][-1]

编辑于 2017-08-09 16:27:25 回复(0)