解决leetcode第3455题最短匹配子字符串

3455.最短匹配子字符串

难度：困难

问题描述

给你一个字符串s和一个模式字符串p，其中p恰好包含两个'*'字符。

p中的'*'匹配零个或多个字符的任何序列。

返回s中与p匹配的最短子字符串的长度。如果没有这样的子字符串，返回-1。

子字符串是字符串中的一个连续字符序列（空子字符串也被认为是合法字符串）。

示例1：

输入：s="abaacbaecebce",p="ba*c*ce"

输出：8

解释：

在s中，p的最短匹配子字符串是"baecebce"。

示例2：

输入：s="baccbaadbc",p="cc*baa*adb"

输出：-1

解释：

在s中没有匹配的子字符串。

示例3：

输入：s="a",p="**"

输出：0

解释：

空子字符串是最短的匹配子字符串。

示例4：

输入：s="madlogic",p="*adlogi*"

输出：6

解释：

在s中，p的最短匹配子字符串是"adlogi"。

提示：

1<=s.length<=105

2<=p.length<=105

s仅包含小写英文字母。

p仅包含小写英文字母，并且恰好包含两个'*'。

问题分析：

思路是将模式字符串p中除*号之外的字符串提取出来，然后在字符串s中去匹配

我们将按left*mid*right的模式提取出三部分left、mid和right，将它们各自在原字符串s中的索引号找到，并以[left，索引号]、[mid，索引号]和[right），索引号]的形式记录在列表中。最后我们再在这个列表中去找长度最短的匹配字符串长度。

根据提取出的left、mid和right的不同，有不同的处理：

如果p=**,直接返回0

如果p=**right或*mid*或left**，直接返回提取出来的字符串right、mid或left的长度

如果p=*mid*right、left**right或left*mid*，则直接找mid*right、left**right和left*mid的最短长度就可以了

最后是p=left*mid*right这种形式，其实也是返回left*right的最短长度，只不过在它们中间一定要有mid的位置，且不能有重叠区间

程序如下：

#从字符串s中找字符串t的索引位置并返回列表
def get_str_index(s,t):n=s.count(t)d=[]m=0for i in range(n):m=s.index(t,m)d.append(m)m=m+1return d#将按p拆分的几部分分别在s中查找对应的索引，并以列表的形式返回
def get_lmr_list(s,p):a=p.split('*')b=[]for i in a:c=get_str_index(s,i)d=[[i,k] for k in c]b.extend(d)b.append([s,len(s)])return b#将按p生成的几部分的索引列表，对输入的两部分求取其中的最短范围，并返回
def get_min_dis(a_list,lmr1,lmr2,lmr3):lmr1_list=[i for i in a_list if i[0]==lmr1]lmr2_list=[i for i in a_list if i[0]==lmr2]if lmr3!='':lmr3_list=[i for i in a_list if i[0]==lmr3]min_dis=max(k[1] for k in a_list)a=[]b=[]for i in lmr1_list:for j in lmr2_list:if j[1]>i[1]+len(lmr1)-1 and True if lmr3=='' else check_mid_in(i[1]+len(lmr1)-1,j[1],lmr3_list):dis=j[1]-i[1]if dis<min_dis:min_dis=disa=ib=jreturn [a,b]def check_mid_in(a,b,c):for i in c:if a<i[1] and i[1]+len(i[0])-1<b:return Trueelse:return False#获取最短匹配子字符串长度
def get_min_str(s,p):temp=get_lmr_list(s,p)a=p.split('*')left=a[0]mid=a[1]right=a[2]if left=='' and mid=='' and right=='':return 0elif left=='' and mid=='' and right in s:return len(right)elif mid=='' and right=='' and left in s:return len(left)elif left=='' and right=='' and mid in s:return len(mid)elif left=='' and mid in s and right in s:a=get_min_dis(temp,mid,right,left)return a[1][1]+len(a[1][0])-a[0][1]elif mid=='' and left in s and right in s:a = get_min_dis(temp, left, right,mid)return a[1][1]+len(a[1][0])-a[0][1]elif right=='' and left in s and mid in s:a = get_min_dis(temp, left, mid,right)return a[1][1]+len(a[1][0])-a[0][1]elif left in s and mid in s and right in s:a = get_min_dis(temp, left, right,mid)if not a[0] and not a[1]:return -1else:return a[1][1]+len(a[1][0])-a[0][1]s=input('pls input s=')
p=input('pls input p=')
print(get_min_str(s,p))