abbreviation.py

"""
https://www.hackerrank.com/challenges/abbr/problem
You can perform the following operation on some string, :

1. Capitalize zero or more of 's lowercase letters at some index i
 (i.e., make them uppercase).
2. Delete all of the remaining lowercase letters in .

Example:
a=daBcd and b="ABC"
daBcd -> capitalize a and c(dABCd) -> remove d (ABC)
"""


defabbr(a: str, b: str) ->bool:
"""
 >>> abbr("daBcd", "ABC")
 True
 >>> abbr("dBcd", "ABC")
 False
 """
n=len(a)
m=len(b)
dp= [[Falsefor_inrange(m+1)] for_inrange(n+1)]
dp[0][0] =True
foriinrange(n):
forjinrange(m+1):
ifdp[i][j]:
ifj<manda[i].upper() ==b[j]:
dp[i+1][j+1] =True
ifa[i].islower():
dp[i+1][j] =True
returndp[n][m]


if__name__=="__main__":
importdoctest

doctest.testmod()