题目详情:
从字符串string开始完整匹配子串sub,返回匹配到的字符个数。
sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到匹配的字符,则说明不能完整匹配。
如果能完整匹配,返回匹配到的字符个数,如果有多种匹配方式,返回匹配字符数最少的那个,如果不能完整匹配,返回-1
输入描述:
第一行输入字符串string,长度小于10000 第二行输入子串sub,长度小于100
输出描述:
从string开头位置完整匹配sub,匹配到的字符个数。
示例1
输入
abcdefg
a?c
输出
3
示例2
输入
aabcddefg
a?c
输出
4
示例3
输入
aabcddefg
b?e
输出
-1
示例4
输入
aabcddefg
a?d
输出
5
代码解答:
s1 = input()
s2 = input()
n,m = len(s1),len(s2)
# 当两个字符串为空时,匹配数量为0输出0
if n == 0 or m == 0:
print(0)
# 当匹配字符串长度大于原字符串时,不能匹配,输出-1
elif n < m:
print(-1)
else:
res = -1
# 当匹配字符串第一个字符不是"?"时,
# 若原字符串与匹配字符串第一个字符不相同,则无法向下继续匹配,跳出,直接输出-1
if s2[0] != "?" and s1[0] != s2[0]:
print(res)
else:
# 分别为原字符串与匹配字符串申请一个指针,并初始化指向第一个字符
j, sj = 0, 0
# 循环移动指针,直至到字符串尾部
while j < n and sj < m:
# 当匹配字符串不是指向"?"时,
# 若两个字符串指向的字符不相同则不能继续匹配直接跳出输出-1
if s2[sj] != "?" and s2[sj] != s1[j]:
break
# 当两个指针指向相同的字符时,两个指针向下移动一格,继续向下匹配
elif s2[sj] == s1[j]:
sj += 1
j += 1
# 当匹配字符串指针指向"?"时,查看"?"匹配数量是否大于3,大于则输出-1
elif s2[sj] == "?":
if j - sj > 3:
res = -1
break
# 若两个字符串下一个指针指向字符相同,则跳过下一个,指针加2,继续向下
if s2[sj+1] == s1[j+1]:
sj += 2
j += 2
# 否则原字符串加一,匹配字符串指针不变,查看"?"最多匹配数量
else:
j += 1
# 若匹配字符串指针已经指向尾部(完全匹配)且结果数小于新的匹配数,则更新
if sj >= m and j <= n and j > res:
res = j
print(res)
版权声明:本文为kingyuan666原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。