Wildcard Match
Python
Hard
2 views
Problem Description
Read string s and pattern p with '?' (any char) and '*' (any sequence). Output YES if pattern matches whole string else NO.
Input Format
Two lines: s then p.
Constraints
len(s),len(p)
Official Solution
import sys
lines=sys.stdin.read().splitlines()
if len(lines)<2: sys.exit(0)
s=lines[0].strip()
p=lines[1].strip()
ns=len(s); np=len(p)
prev=[False]*(np+1)
prev[0]=True
for j in range(1,np+1):
prev[j]=prev[j-1] and p[j-1]=='*'
for i in range(1,ns+1):
cur=[False]*(np+1)
for j in range(1,np+1):
if p[j-1]=='*':
cur[j]=cur[j-1] or prev[j]
elif p[j-1]=='?' or p[j-1]==s[i-1]:
cur[j]=prev[j-1]
prev=cur
sys.stdout.write('YES' if prev[np] else 'NO')
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!