-
Notifications
You must be signed in to change notification settings - Fork 77
/
Abbrevation.py
40 lines (31 loc) · 962 Bytes
/
Abbrevation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/bin/python3
import math
import os
import random
import re
import sys
def abbreviation(a, b):
m, n = len(a), len(b)
dp = [[False]*(m+1) for _ in range(n+1)]
dp[0][0] = True
for i in range(n+1):
for j in range(m+1):
if i == 0 and j != 0:
dp[i][j] = a[j-1].islower() and dp[i][j-1]
elif i != 0 and j != 0:
if a[j-1] == b[i-1]:
dp[i][j] = dp[i-1][j-1]
elif a[j-1].upper() == b[i-1]:
dp[i][j] = dp[i-1][j-1] or dp[i][j-1]
elif not (a[j-1].isupper() and b[i-1].isupper()):
dp[i][j] = dp[i][j-1]
return "YES" if dp[n][m] else "NO"
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
q = int(input())
for q_itr in range(q):
a = input()
b = input()
result = abbreviation(a, b)
fptr.write(result + '\n')
fptr.close()