[Hackerrank] [Medium] Abbreviation

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

Abbreviation | HackerRank

풀이

• 두 개의 문자열 a, b를 입력받음. 문자열 a를 다음 두 가지 방법을 사용해 문자열 b를 만들 수 있으면 "YES"를, 아니면 "NO"를 출력하는 문제
  • 문자열 a의 소문자를 대문자로 0개 이상 바꿀 수 있음.
  • 문자열 a의 소문자를 모두 제거.
  • a = AbcDE, b = ABDE일 때, ABcDE로 b -> B로 바꾼 뒤, 소문자를 모두 제거하면 ABDE가 되므로 b를 만들 수 있음.
• Dynamic programming을 사용해서 품.
  • 처음에는 대소문자 상관없이 a의 j번째 문자열 = b의 i번째 문자열이면 dp[ i - 1 ] [ j - 1 ]의 값을 가져오면 될줄 알았는데, 매칭된 문자가 대소문자일 때를 따로 생각해야 함.
  • a가 소문자일 때, 이는 제거 가능하기 때문에 dp[ i ] [ j - 1 ]의 값도 고려해 값을 update해야 함.
  • 매칭이 안되더라도 a가 소문자일 경우에, dp[ i ] [ j - 1 ] 값으로 update함.
    • j - 1일 때는, j번째 이전까지의 dp 값을 의미함( a의 j 번째 문자를 삭제한 case )

def abbreviation(a, b):
    dp = [[False]*(len(A)+1) for _ in range(len(B)+1)]
    dp[0][0] = True

    for i in range(len(B)+1):
        for j in range(len(A)+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:
                # 문자열이 그냥 맞을 경우 dp에 저장된 이전 문자열까지의 매칭 결과를 가져옴.
                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 a[j-1].islower():
                    dp[i][j] = dp[i][j-1]
    return "YES" if dp[n][m] else "NO"