算法练习，字符串交错组成-面试常考算法题（九）

对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2…，其中Ui < Ui+1，且A[Ui]K < A[Ui+1]。
给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。

测试样例：[2,1,4,3,1,5,6],7
返回：4

本题知识点：动态规划排序查找
对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3…Un和V1,V2,V3…Vn,其中Ui<Ui+1，Vi<Vi+1。且A[Ui] == B[Vi]。
给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例： “1A2C3D4B56”,10,”B1D23CA45B6A”,12
返回：6

本体知识点：动态规划、贪心
对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,…Vn，其中Ui + 1 == Ui+1，Vi + 1 %= Vi+1，同时Ui == Vi。给定两个字符串A和B，同时给定两串的长度n和m。

测试样例： “1AB2345CD”,9,”12345EF”,7
返回：4

本体知识点：动态规划、贪心
对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。
给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。

测试样例：”abc”,3,”adc”,3,5,3,100
返回：8

本题知识点：动态规划
对于三个字符串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
返回：6

本题知识点：动态规划

解析

给出Decorator memo，memo构建一个缓存。调用函数时先查找缓存中是否存在计算好的值，只有不存在时才会调用函数进行计算。

def memo(f):
    cache = {}
    def func(*a):
        try:
            return cache[a]
        except:
            cache[a]=f(*a)
            return cache[a]
    return func

容易知道若$U=[A_{i1},A{i2},\ldots,A{i_n}]$为一个上升子序列，若存在$K_j$满足$j<i_1$且$Kj<A{i_1}$，则$K_j \cup U$依然是一个上升子序列。这样就将问题分解为子问题，可以使用动态规划求解。

自顶向下方法：

@memo
def findLongest(A, n, biggerthan=0):
    if n==0:
        return 0
    else:
        return max(findLongest(A[i+1:], n-i-1,A[i]) for (i,p) in enumerate(A) if p>biggerthan)+1
print findLongest([2,1,4,3,1,5,6], 7)

类似于题1，设dp[i][j]表示A[i:]与B[j:]的最长公共子串长度，则
dp[i][j]=1+dp[i+1][j+1] if A[i]==B[j] else max(…)

自底向上方法：

def findLCS(A, n, B, m):
    dp = [[0 for col in range(m+1)] for row in range(n+1)]
    for r in reversed(range(n)):
        for c in reversed(range(m)):
            if A[r]==B[c]:
                dp[r][c]=1+dp[r+1][c+1]
            else:
                dp[r][c]=max(dp[latterr][latterc] for latterr in range(r,n+1) for latterc in range(c,m+1))
    return dp
dp = findLCS('123A456', 7, 'B123456', 7)
print dp[0][0]

自顶向下方法：

@memo
def findLCS(A, n, B, m):
    if n==0 or m==0:
        return 0
    elif A[0]==B[0]:
        return findLCS(A[1:], n-1, B[1:], m-1)+1
    else:
        try:
            return max(findLCS(A[i:], n-i, B[j:], m-j) for i in range(0,n) for j in range(0,m) if not (i==0 and j==0))
        except:
            return 0

类似于题二，只需要改动A[i]!=B[j]时的操作，

def findLongest(A, n, B, m):
    dp = [[0 for col in range(m+1)] for row in range(n+1)]
    for r in reversed(range(n)):
        for c in reversed(range(m)):
            if A[r]==B[c]:
                dp[r][c]=1+dp[r+1][c+1]
            else:
                dp[r][c]=0
    return dp
dp = findLongest('1AB2345CD', 9, '12345EF', 7)
print max(i for j in dp for i in j)

求编辑距离的经典问题，只需要为每一种操作赋上权值

def findMinCost(A, n, B, m, c0, c1, c2):
    dp = [[0 for col in range(m+1)] for row in range(n+1)]
    for r in range(n+1):
        dp[r][0] = r * c1  # delete
    for c in range(m+1):
        dp[0][c] = c * c0  # insert
    for r in range(1, n+1):
        for c in range(1, m+1):
            dp[r][c] = min([dp[r - 1][c] + c0,  # insert
                            dp[r][c - 1] + c1,  # delete
                            dp[r - 1][c - 1] + (c2 if A[r-1] != B[c-1] else 0)])  # substitute
            print dp
    return dp[3][3]
print findMinCost("abc", 3, "adc", 3, 5, 3, 100)

相当于搜索一颗二叉树，左儿子就是AC两串字符头匹配，右儿子就是BC两串头匹配。

@memo
def chkMixture(A, n, B, m, C, v):
    if n+m!=v:
        return False
    if n==0 and m==0 and v==0:
        return True
    else:
        rst = False
        if n!=0 and A[0]==C[0]:
            rst = rst or chkMixture(A[1:], n-1, B, m, C[1:], v-1)
        if not rst and m!=0 and B[0]==C[0]:
            rst = rst or chkMixture(A, n, B[1:], m-1, C[1:], v-1)
        return rst