题解 | #最长上升子序列(一)#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @param pattern string字符串 
# @return bool布尔型
#
class Solution:
    def match(self , str1 , pattern ):
        # write code here
        if not str or not pattern:
            return False
        m,n = len(str1),len(pattern)
        if pattern[0]== '*':
            return False
        mark = [[False]*(n+1) for i in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i==0 :
                    if j==0:
                        mark[i][j] = True
                    elif pattern[j-1]!='*':
                        mark[i][j] = False
                    elif j>=2:
                        mark[i][j] = mark[i][j-2]
                    else:
                        mark[i][j] = False
                    continue
                if j==0:
                    mark[i][j] = False
                    continue
                if str1[i-1]==pattern[j-1] or pattern[j-1]=='.':
                    mark[i][j] = mark[i-1][j-1]
                    continue
                if pattern[j-1]=='*' and j>1:
                    if (pattern[j-2]=='.' or pattern[j-2]==str1[i-1]):
                        mark[i][j] = mark[i-1][j]
                    if not mark[i][j]:
                        mark[i][j] = mark[i][j-2]
#         for i in mark:
#             print(i)
        return mark[m][n]