题目描述 或 剑指offer19.正则表达式匹配

Shopee2019年笔试题：在Linux Shell命令下通配符’‘表示0个或多个字符, 现编写一段代码实现通配符’‘的功能，注意只需要实现’*’, 不用实现其他通配符。

数据读入：

需要读入两行line，怎么做：
遇到""空字符，break；
空字符前（第一行）的赋值给t，之后的input()（第二行）赋值给s；

while True:
    line = sys.stdin.readline().strip()
    if line == '':    #一直读入，直到遇到空字符break
        break
    t = line        
    print('t:', t)    #o*m 为第一行输入
    s = input()     
    print('s:', s)    #shopeemobile.com

或者直接

t = input()
s = input()

代码 通配符/正则表达式

#深度优先遍历，动态规划，回溯算法
import sys
def DFS(i, j):
    if j == len(t):		#j到头了表示t匹配成功
        S.add(i)
        return
    if i == len(s):		#i==len(s)表明当前已经深度优先到最深了，源串已经匹配结束
        return
    if s[i] == t[j]:	#如果是字母本身匹配，看下一组是否匹配DFS(i+1, j+1)
        DFS(i+1, j+1)
    elif t[j] == '*':
        DFS(i, j+1)		#s不变，t往下，*代表0个
        DFS(i+1, j)		#s往下，t不变，*代表两个
        DFS(i+1, j+1)	#s往下，t不变，*代表1个
    return
while True:
    line = sys.stdin.readline().strip()
    if line == '':    #一直读入，直到遇到空字符break
        break
    t = line			#target目标串
    #print('t:', t)    #o*m 为第一行输入
    s = input()     	#SOURCE源串
    #print('s:', s)    #shopeemobile.com
    S = set()
    #print("S是：", S)    #set()
    flag = False
    # i is the start idx of s
    # S includes all the end index it that s[i:it] matches t
    for i in range(len(s)):
        if s[i] == t[0] or t[0] == '*':    #可以开始遍历的条件
            DFS(i, 0)        #s串从i开始，j串从0开始
        if len(S) != 0:
            flag = True		#当S有值时，flag为True
            for it in sorted(S):	#sorted(S)不改变S，按从小到大顺序重排令赋值
                if it > i:			#S中存储的it是s串中当前i开头，匹配成功的尾巴在s中的index
                    print(i, it-i)	#对S进行sorted排序后（从小到大），i=2时候，[7，16]，所以返回（2，5）和（2，14）
        S.clear()
    if not flag:		#如果flag为false，直接返回（-1,0）
        print(-1, 0)