디코딩 방법

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 시스코 데이터 브릭 Facebook 골드만 삭스 구글 JP 모건 Microsoft 모건 스탠리 (Morgan Stanley) 신탁 사각형.
동적 프로그래밍 조회수 98

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

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) 번째 인덱스 요소와 병합하여 유효한 두 자리 숫자를 형성 할 수 있는지 모든 단계에서 확인합니다.

  1. s [i]! = '0'이면 dp [i] + = dp [i + 1]
  2. s [i] == '1'이면 dp [i] + = dp [i + 2]
  3. 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 배열에 각 단계의 방법 수를 저장하기 때문에 선형 공간 복잡성이 발생합니다.

참조

균열 시스템 설계 인터뷰
Translate »