FilesExpand file tree

 master

/

abbreviation.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (33 loc) · 966 Bytes

 master

/

abbreviation.py

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (33 loc) · 966 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

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)

"""

def abbr(a, b):

"""

>>> abbr("daBcd", "ABC")

True

>>> abbr("dBcd", "ABC")

False

"""

n = len(a)

m = len(b)

dp = [[False for _ in range(m + 1)] for _ in range(n + 1)]

dp[0][0] = True

for i in range(n):

for j in range(m + 1):

if dp[i][j]:

if j < m and a[i].upper() == b[j]:

dp[i + 1][j + 1] = True

if a[i].islower():

dp[i + 1][j] = True

return dp[n][m]

if __name__ == "__main__":

# print(abbr("daBcd", "ABC")) # expect True

import doctest

doctest.testmod()