Python의 디코딩 방법

A에서 Z까지의 문자가 포함된 메시지가 'A' → 1, 'B' → 2 ... 'Z' → 매핑을 사용하여 숫자로 인코딩되고 있다고 가정합니다. 26. 따라서 숫자만 포함하는 비어 있지 않은 문자열이 하나 있다면 디코딩할 수 있는 방법의 수를 찾아야 합니다. 따라서 문자열이 "12"와 같으면 "AB" 또는 "L"로 만들 수 있으므로 두 가지 가능한 방법이 있습니다. 따라서 답은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

동적 프로그래밍을 사용하여 이 문제를 해결할 것입니다.
n :=s의 길이
dp :=n개의 0이 있는 배열
s[0]이 '0'이 아니면 dp[0] :=1
1 ~ n – 1 범위의 i에 대해
- x :=s[i] 정수로, y :=인덱스 i – 1에서 정수로 i + 1까지 s의 부분 문자열
- x>=1이고 y <=9이면 dp[i] :=dp[i] + dp[i – 1]
- y>=10이고 y <=26인 경우
  - i – 2>=0이면 dp[i] :=dp[i] + dp[i – 2]이고, 그렇지 않으면 dp[i]를 1만큼 증가
dp의 마지막 요소를 반환

예시(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def numDecodings(self, s):
      n = len(s)
      dp = [0 for i in range(n)]
      if s[0]!='0':
         dp[0]=1
      for i in range(1,n):
         x = int(s[i])
         y = int(s[i-1:i+1])
         if x>=1 and x<=9:
            dp[i]+=dp[i-1]
         if y>=10 and y<=26:
            if i-2>=0:
               dp[i]+=dp[i-2]
            else:
               dp[i]+=1
      return dp[-1]
ob1 = Solution()
print(ob1.numDecodings("226"))

입력

"226"

Python의 디코딩 방법

예시(파이썬)

입력

출력