C++LeetCode 구현(91.디 코딩 방법)

[LeetCode]91.디 코딩 방법
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
이 문 제 는 디 코딩 방법 을 요구 하 는데,이전 문제 와 같다.  Climbing Stairs  매우 비슷 하지만 다른 제한 조건 도 있다.예 를 들 어 한 자릿수 일 때 0 이 될 수 없고 두 자릿수 가 26 보다 크 면 안 된다.그 10 명의 숫자 도 0 이 될 수 없다.이런 제한 조건 을 제외 하고 사다 리 를 오 르 는 것 과 거의 다 르 지 않 고 특수 한 피 보 나치 수열 이 라 고 할 수 있다.물론 동적 계획 인 Dynamci Programming 으로 풀 어야 한다.1 차원 dp 배열 을 만 듭 니 다.그 중에서 dp[i]는 s 의 앞 i 문자 로 구 성 된 하위 문자열 의 디 코딩 방법 을 나타 내 는 갯 수 입 니 다.길 이 는 입력 배열 보다 1 이 많 고 dp[0]를 1 로 초기 화 합 니 다.현재 상태 전이 방정식 을 찾 으 러 왔 습 니 다.dp[i]의 값 은 이전의 상태 와 밀접 한 관 계 를 가지 고 있 습 니 다.문제 중의 예 2 로 분석 하 세 요.i=1 일 때 대응 하 는 s 중의 문 자 는 s[0]='2'입 니 다.한 가지 분할 방법 만 있 습 니 다.바로 2 입 니 다.s[0]가 0 이 되 어 서 는 안 됩 니 다.그러면 분리 할 수 없습니다.i=2 일 때 대응 하 는 s 의 문 자 는 s[1]='2'입 니 다.s[1]가 0 이 아니 기 때문에 따로 나 눌 수 있 습 니 다.기 존의 dp[i-1]의 모든 상황 에서 하나의 단독 2 를 추가 할 수 있 습 니 다.그러면 dp[i]는 적어도 dp[i-1]과 같은 분할 상황 이 있 을 수 있 습 니 다.그 다음 에 앞의 숫자 와 맞 출 수 있 는 지 여 부 를 봐 야 합 니 다.만약 에 맞 춘 두 자릿수 가 26 보다 작 으 면그리고 10 보다 크 면(두 자릿수 의 높 은 자리 가 0 이 될 수 없 기 때문에)이전 dp[i-2] 의 모든 상황 에서 이 두 자릿수 를 더 하기 때문에 최종 dp[i]=dp[i-1]+dp[i-2]는 피 보 나치 수열 의 성질 과 일치 하 는 것 을 발견 한 것 입 니까?그래서 0 은 매우 특수 한 존재 입 니 다.만약 에 현재 위치 가 0 이 라면 따로 분리 할 수 없습니다.즉,dp[i-1]을 추가 하지 못 하면 앞의 숫자 구성 이 10 보다 크 고 26 보다 작은 지 볼 수 있 습 니 다.할 수 있다 면 dp[i-2]를 추가 할 수 있 습 니 다.그렇지 않 으 면 0 으로 유지 할 수 밖 에 없습니다.구체 적 인 조작 절 차 는 옮 겨 다 니 는 과정 에서 모든 숫자 에 대해 0 인지 아 닌 지 를 먼저 판단 하 는 것 이다.만약 에 dp[i]를 0 으로 부여 하고 그렇지 않 으 면 dp[i-1]의 값 을 부여 한 다음 에 배열 의 앞 자리 가 존재 하 는 지 를 보고 앞 자리 가 1 인지 만족 하거나 현재 자리 와 함께 구 성 된 두 자릿수 가 26 보다 크 지 않 으 면 현재 dp[i]값 에 dp[i-2]를 더 하 는 것 이다.마지막 으로 dp 배열 의 마지막 값 을 되 돌려 주면 됩 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java 해법 1:

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

아래 의 이런 방법 은 위의 방법의 사고 와 마찬가지 로 쓰기 만 약간 다르다.
C++해법 2:

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java  해법 2:

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            if (i >= 2 && (s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

우 리 는 공간 복잡 도가 O(1)인 해법 을 다시 살 펴 보 겠 습 니 다.두 개의 변수 a,b 로 각각 s[i-1]과 s[i-2]의 디 코딩 방법 을 표시 한 다음 에 i=1 부터 옮 겨 다 니 는 것 입 니 다.즉,문자열 의 두 번 째 문자 입 니 다.현재 문자 가'0'이면 현재 문 자 를 단독으로 나 눌 수 없고 앞의 문자 와 함께 만 할 수 있 음 을 판단 합 니 다.먼저 a 를 0 으로 부 여 했 습 니 다.그리고 앞의 문 자 를 보 세 요.만약 에 앞의 문자 가 1 이나 2 일 때 a=a+b 를 업데이트 할 수 있 습 니 다.그리고 b=a-b 는 사실 b 할당 값 이 이전의 a 입 니 다.이런 조건 을 만족 시 키 지 않 으 면 b=a 는 코드 를 다음 과 같이 참조 합 니 다.
C++해법 3:

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int a = 1, b = 1, n = s.size();
        for (int i = 1; i < n; ++i) {
            if (s[i] == '0') a = 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
};

자바 해법 3:

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int a = 1, b = 1, n = s.length();
        for (int i = 1; i < n; ++i) {
            if (s.charAt(i) == '0') a = 0;
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
}

C++구현 LeetCode(91.디 코딩 방법)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 디 코딩 방법 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!