Decode Ways 문제에서 우리는 비어 있지 않은 현 숫자 만 포함하는 경우 다음 매핑을 사용하여 디코딩하는 총 방법 수를 결정합니다.
'A' -> 1 'B' -> 2 ... 'Z' -> 26
차례
예
S =“123”
이 문자열을 디코딩하는 방법은 3 개입니다.
문제를 자세히 살펴보면 0을 제외한 모든 한 자리 숫자가 유효하지만 두 자리 숫자의 경우 10에서 26 사이의 숫자 만 유효하다는 것을 알 수 있습니다.
따라서 우리는 모든 지수에서 두 단계:
1. 문자열의 i 번째 요소가 '0'이 아닌 경우 매핑을 사용하여 i 번째 인덱스로 시작하는 문자열을 디코딩하는 한 가지 방법이 있습니다.
'A' -> 1 'B' -> 2 …. 'I' -> 9
2. i 번째 및 (i + 1) 번째 인덱스를 병합하여 다음 매핑을 사용하여 유효한 숫자를 형성 할 수있는 경우 :
'J' -> 10 'K' -> 11 …. 'Z' -> 26
그런 다음 i 번째 인덱스로 시작하는 문자열을 디코딩하는 또 다른 방법이 있습니다.
디코딩 방법을위한 알고리즘
단계 1: 크기 n의 1D 배열을 XNUMX으로 선언하고 초기화합니다.
단계 2: (n-1) 번째 인덱스 (Base case)에서 시작하고 끝나는 문자열을 디코딩 할 수 있는지 확인합니다.
단계 3: 루프를 실행하고 i 번째 인덱스 요소를 유효한 한 자리 숫자로 사용할 수 있는지 또는 (i + 1) 번째 인덱스 요소와 병합하여 유효한 두 자리 숫자를 형성 할 수 있는지 모든 단계에서 확인합니다.
- s [i]! = '0'이면 dp [i] + = dp [i + 1]
- s [i] == '1'이면 dp [i] + = dp [i + 2]
- s [i] == '2'및 s [i + 1] <= '6'이면 dp [i] + = dp [i + 2]
단계 4: dp [0]을 반환합니다.
실시
디코드 방식을위한 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
int n=s.length();
int dp[n+1];
memset(dp,0,sizeof(dp));
dp[n]=1;
if(s[n-1]!='0'){ //if the last chararcter is not zero then we have one way to decode it
dp[n-1]=1;
}
for(int i=n-2;i>=0;i--){
if(s[i]!='0'){
dp[i]+=dp[i+1];
}
if(s[i]=='1'){
dp[i]+=dp[i+2];
}
if(s[i]=='2'){
if(s[i+1]<='6'){
dp[i]+=dp[i+2];
}
}
}
return dp[0];
}
int main(){
string s="452625";
cout<<"The number of ways to decode the given string is: "<<numDecodings(s);
}
The number of ways to decode the given string is: 4
디코드 방식을위한 JAVA 프로그램
public class Main
{
public static int numDecodings(String s) {
int n=s.length();
int[] dp=new int[n+1];
dp[n]=1;
if(s.charAt(n-1)!='0'){ //if the last chararcter is not zero then we have one way to decode it
dp[n-1]=1;
}
for(int i=n-2;i>=0;i--){
dp[i]=0;
if(s.charAt(i)!='0'){
dp[i]+=dp[i+1];
}
if(s.charAt(i)=='1'){
dp[i]+=dp[i+2];
}
if(s.charAt(i)=='2'){
if(s.charAt(i+1)<='6'){
dp[i]+=dp[i+2];
}
}
}
return dp[0];
}
public static void main(String[] args) {
String s="23572";
System.out.println("The number of ways to decode the given string is: "+numDecodings(s));
}
}
The number of ways to decode the given string is: 2
디코딩 방식에 대한 복잡성 분석
시간 복잡도 : O (n) 여기서 n은 주어진 문자열의 길이입니다.
주어진 문자열을 한 번만 통과하므로 복잡성은 O (n)입니다.
공간 복잡성 : O (n) dp 배열에 각 단계의 방법 수를 저장하기 때문에 선형 공간 복잡성이 발생합니다.
