[HackerRank] Abbreviation - python

문제

https://www.hackerrank.com/challenges/abbr/problem

풀이

• DP 사용
  • 소문자 문자열은 제거 가능하다
  • 소문자 문자열을 대문자로 바꿀 수 있음
• dp[i][j] 차례에서 일치하기 때문에 a[i]가 소문자라면 dp[i+1][j] = 1
• 두 번째 for 문에서 len(b) + 1 한 이유는 b 보다 a문자열이 더 길 때, 뒤에 일치하지 않는 대문자가 올 수 있기 때문에 마지막에 한 번 더 확인해줘야 한다.

def abbreviation(a, b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    dp[0][0] = 1
    for i in range(len(a)):
        for j in range(len(b)+1):
        	# 현재 차례에서 일치하는 경우
            if dp[i][j]:
            	# 대문자로 바꿨을 때 만족하는 경우 
                if j < len(b) and a[i].upper() == b[j]:
                    dp[i+1][j+1] = 1
				# 소문자는 제거 가능 
                if a[i].islower():
                    dp[i+1][j] = 1
    result ="NO"
    if dp[-1][-1]:
        result = "YES"
    return result
                

피드백 환영!