Decode Ways
대문자로 된 메시지는 A = 1, B = 2 등으로 Z = 26까지 인코딩되며, 코드는 구분자 없이 이어서 작성됩니다. 숫자 문자열 s가 주어지면, 이 문자열을 만들어 냈을 수 있는 메시지의 개수를 반환하세요.
문자는 숫자 하나 또는 서로 인접한 숫자 두 개로 읽으며, 코드는 0으로 시작하지 않습니다. 06은 6이 아니며, 단독으로 있는 0은 문자가 아닙니다. 가능한 해석이 없으면 0을 반환하세요.
함수
- sstring
- 디코딩할 숫자 문자열
- 반환값integer
- s로 인코딩되는 문자 메시지의 수
제약 조건
1 ≤ s.length ≤ 100s에는0부터9까지의 숫자만 포함되며,0으로 시작할 수도 있습니다.-
s의 모든 접두사와 모든 접미사의 읽기 수는231보다 적으므로, 정답과 계산 과정에서 구하는 모든 개수는 부호 있는 32비트 정수에 들어갑니다.
예제
- 입력
- s = "2611"
- 출력
- 4
- 설명
- 네 가지 판독값은
2 6 1 1(BFAA),26 1 1(ZAA),2 6 11(BFK),26 11(ZK)입니다. 61은 26보다 크므로 가운데 숫자들은 절대로 짝을 이루지 않습니다.
- 입력
- s = "1203"
- 출력
- 1
- 설명
0은 앞에 있는2와 짝을 이루어20이 되어야 하며, 이로 인해1 20 3(ATC)이 됩니다.12를 먼저 읽으면0이 홀로 남고,03은 0으로 시작합니다.
- 입력
- s = "06"
- 출력
- 0
- 설명
- 첫 번째 문자는
0으로 시작해야 합니다.0하나만으로는 문자가 아니고06은 코드가 아니므로, 어떤 메시지도 이 문자열을 만들지 않습니다.
후속 질문
s에 *도 들어갈 수 있고, 이는 1부터 9까지의 숫자 중 하나를 나타낸다면 어떨까요? 10^9+7로 나눈 나머지를 구하면서 O(n) 시간에 해석 가능한 경우의 수를 셀 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
첫 번째 숫자만 살펴보세요. 첫 번째 문자를 읽는 방법은 몇 가지이며, 각각의 방법을 선택한 후 문자열에 남는 것은 무엇인가요?
문자열의 나머지 부분이 몇 개의 읽기를 가지는지는 나머지 부분이 어디서 시작하는지에만 달려 있으며, 어떻게 그 지점에 도달했는지에는 달려 있지 않습니다. 각 시작점을 한 번씩 세고 그 개수를 재사용하세요.
ways(i)가 처음i자리 숫자의 해독 경우의 수를 세도록 하자. 여기서ways(0) = 1이다. 숫자i-1이0이 아니면ways(i-1)을 더하고, 위치i앞의 두 숫자가 10에서 26 사이의 수를 이루면ways(i-2)를 더한다. 마지막 두 개의 경우의 수만 있으면 된다.
풀이
각 숫자는 혼자 하나의 글자에 대응하거나 이웃 숫자와 합쳐지므로, 해석 가능한 경우의 수는 피보나치 수처럼 늘어납니다. 숫자 1이 45개 있으면 경우의 수는 1836311903입니다. 이를 모두 나열하는 것은 불가능하지만, 해석을 끝내는 방법은 도달한 위치에만 달려 있으므로 각 위치는 한 번만 세면 됩니다. 0은 10 또는 20의 끝에만 올 수 있습니다.
재귀를 사용해 두 가지 해석을 모두 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
인덱스 i에서 0은 어떤 문자도 시작하지 않으므로, 해당 경로에서는 해석이 나오지 않습니다. 그렇지 않으면 숫자 하나를 읽고 i+1부터 나머지를 셉니다. 두 숫자가 10에서 26을 이루면 두 숫자를 모두 읽고 i+2부터 세는 경우도 고려합니다. 두 선택지는 서로 다른 첫 글자를 나타내므로, 중복 없이 두 경우의 수를 더할 수 있으며 끝에 도달하면 해석 하나가 완성됩니다.
아무것도 저장해 두지 않으므로 호출 횟수는 피보나치 규칙을 따릅니다. 숫자 1이 45개 있으면 호출은 약 5 × 10^9회입니다. 답이 0인 경우도 더 빠르지 않습니다. 숫자 1이 44개, 숫자 3이 55개, 마지막에 0이 있으면 약 10^11회 호출됩니다. 숫자 1로 이루어진 모든 해석이 마지막 숫자에서야 중단되기 때문입니다.
알고리즘
waysFrom(i)는 인덱스i부터 끝까지 숫자를 읽는 방법의 수를 셉니다.- 문자열의 끝에 도달하면 1을 반환합니다.
0이면 0을 반환합니다. - 그렇지 않으면
waysFrom(i+1)을 반환하고, 숫자i와i+1이 26 이하의 수를 이루는 경우waysFrom(i+2)도 더합니다. - 정답은
waysFrom(0)입니다.
def numDecodings(s):
n = len(s)
def ways_from(i):
# The number of ways to decode s[i:].
if i == n:
return 1 # nothing left: one finished reading
if s[i] == "0":
return 0 # no letter code starts with 0
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
return ways
return ways_from(0)메모를 사용한 재귀
핵심 아이디어
재귀는 같은 질문을 여러 번 합니다. "11111"에서 인덱스 3부터의 개수는 1 1 1 뒤에, 11 1 뒤에, 그리고 1 11 뒤에 필요하며, 인덱스 3부터의 숫자에만 의존하므로 매번 같은 값입니다. 각 개수를 처음 계산할 때 저장하고, 0도 실제 개수이므로 아직 계산하지 않은 슬롯은 -1로 표시하세요.
n개의 위치를 각각 한 번씩 계산하며, 각 계산에는 일정한 작업만 필요합니다. 따라서 시간은 O(n)입니다. 메모와 호출 스택은 O(n)의 공간을 사용하며, 깊이는 최대 100회 호출입니다.
알고리즘
- 각 인덱스에 하나씩,
memo를-1로 채웁니다. waysFrom(i)에서 문자열의 끝에 도달하면 1을 반환하고,memo[i]가-1이 아니면memo[i]를 반환합니다.- 그렇지 않으면 일반 재귀에서처럼 개수를 세고, 0도 포함해 그 개수를
memo[i]에 저장한 다음 반환합니다.
def numDecodings(s):
n = len(s)
memo = [-1] * n # memo[i]: ways to decode s[i:], -1 until worked out
def ways_from(i):
if i == n:
return 1
if memo[i] != -1:
return memo[i]
ways = 0
if s[i] != "0":
ways = ways_from(i + 1) # read one digit
if i + 1 < n and int(s[i:i + 2]) <= 26:
ways += ways_from(i + 2) # read two digits, 10 to 26
memo[i] = ways
return ways
return ways_from(0)두 개의 카운터를 사용하는 상향식 방식
핵심 아이디어
대신 접두사의 수를 세세요. ways(i)를 처음 i개 숫자를 읽는 방법의 수라고 합시다. 마지막 문자는 숫자 i-1 하나일 수 있으며, 이 경우 숫자가 1부터 9까지여야 하고 ways(i-1)개의 읽는 방법이 남습니다. 또는 숫자 i-2와 i-1을 함께 사용할 수 있으며, 이 경우 두 숫자가 10부터 26까지를 이루어야 하고 ways(i-2)개의 읽는 방법이 남습니다. 조건을 만족하는 경우의 수를 더하세요. 빈 접두사는 읽는 방법이 하나이므로 ways(0) = 1입니다.
"1203"에서는 개수가 1, 2로 늘었다가 0에서 다시 1이 됩니다. 20만 가능하고, 그 경우 2 앞의 개수를 이어받기 때문입니다. 3은 단독으로 읽을 수 있으므로 개수는 1로 유지됩니다. 각 개수는 두 칸 앞의 값을 참조하므로, 표 대신 변수 두 개를 사용합니다. 시간은 O(n), 공간은 O(1)입니다.
알고리즘
twoBack = 0과oneBack = 1로 설정합니다. 이는 빈 접두사의 개수입니다.- 각 인덱스
i에 대해 숫자i가0이 아니면current를oneBack으로 설정하고, 그렇지 않으면 0으로 설정합니다. i ≥ 1이고 숫자i-1이0이 아니며 숫자i-1과i가 26 이하를 이루면twoBack을 더합니다.- 이동합니다:
twoBack = oneBack으로 설정한 다음oneBack = current로 설정합니다. oneBack을 반환합니다.
def numDecodings(s):
# ways(i) counts the readings of the first i digits; ways(0) = 1.
two_back, one_back = 0, 1 # ways(i-1) and ways(i) before digit i is read
for i in range(len(s)):
current = 0
if s[i] != "0":
current = one_back # digit i is a letter on its own
if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
current += two_back # digits i-1 and i form one letter, 10 to 26
two_back, one_back = one_back, current
return one_back
함정과 경계 사례
0을 문자로 취급하거나06을 6으로 취급하는 것."30","100","06"은 모두 0개의 해석 결과를 가집니다.≤ 26만으로 두 자리 조각을 검사하는 것.05는 숫자로는 5이지만 코드로는 유효하지 않으므로, 첫 번째 자리가0이 아닌지 확인하세요.- 알 수 없는 메모 슬롯을 0으로 표시하는 것. 그러면 해석 결과가 0개인 위치는 저장된 것으로 간주되지 않습니다. 1이 44개, 3이 55개이고 마지막에
0이 있는 경우, 호출 횟수는 다시 약10^11이 됩니다. - 인덱스 0 앞의 숫자를 읽는 것.
i ≥ 1일 때만 두 자리 검사를 하세요. Python에서s[-1]은 마지막 숫자를 조용히 읽습니다. s를 하나의 숫자로 바꾸는 것. 숫자가 100자리라면 어떤 정수 유형에도 들어가지 않으며, 결과를 바꾸는 앞쪽의 0도 사라집니다.
자주 묻는 질문3
Decode Ways의 시간 복잡도는 무엇인가요?
상향식 풀이에서는 각 숫자를 한 번씩 읽고 일정한 작업을 수행하므로 시간은 O(n), 추가 공간은 O(1)입니다. 메모이제이션을 사용한 재귀도 시간은 O(n)이지만 공간은 O(n)을 사용합니다. 일반 재귀의 시간 복잡도는 지수적입니다. 1로만 이루어진 문자열에서는 호출 횟수가 1.618^n처럼 증가합니다.
Decode Ways는 Climbing Stairs와 어떤 관련이 있나요?
둘 다 1칸과 2칸 계단으로 한 줄을 채우는 방법의 수를 셉니다. Climbing Stairs에서는 모든 계단을 밟을 수 있으므로 경우의 수는 피보나치 수입니다. Decode Ways에서는 한 자리 계단은 1부터 9까지, 두 자리 계단은 10부터 26까지여야 하므로 조건이 성립할 때만 각 항을 더합니다.
Decode Ways에서 0은 어떻게 처리하나요?
0은 혼자서는 절대 문자가 될 수 없으므로, 앞에 있는 숫자와 짝을 이루어 10 또는 20이 되어야 합니다. 1이나 2 뒤에 올 때만 두 자리 앞의 개수를 더하고, 그 외에는 아무것도 더하지 않습니다. 맨 앞의 0, 연속된 두 개의 0, 또는 3부터 9까지의 숫자 뒤에 오는 0은 0을 반환합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def numDecodings(s):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
s = "2611"
예상 출력
4