Decode Ways

2023 단어 자바동적 계획
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
1 차원 동적 계획 에 속 하 는 문 제 는 먼저 dp 배열 을 구성 합 니 다. 문제 에서 숫자 1 - 26 만 이 합 법 적 인 숫자 이 고 '0' 이 나 올 때 디 코딩 할 수 없습니다.따라서 우 리 는 먼저 문자열 의 첫 번 째 문자 가 '0' 인지 아 닌 지 를 판단 할 수 있 습 니 다. 만약 '0' 이 라면 우 리 는 0 으로 직접 돌아 갈 수 있 습 니 다. 물론 문자열 자체 가 비어 있 으 면 0 으로 바로 돌아 갈 수 있 습 니 다.만약 0 이 아니라면, 이때 우 리 는 dp [0] = 1 에 대응 하여 첫 번 째 문 자 는 하나의 디 코딩 방식 만 있 습 니 다. i 번 째 문자 가 '0' 이 아니라면 가능 한 상황 은 적어도 dp [i - 1] 가지 가 있 습 니 다. 그리고 우 리 는 i 번 째 문자 와 i - 1 문자 로 구 성 된 숫자 가 1 - 26 사이 에 있 는 지 확인 합 니 다. 만약 에 i 번 째 문 자 는 모두 dp [i - 1] + dp [i - 2] 가지 가 있 습 니 다.이때 (i > 1, i = = 1 일 때 dp [i - 1] + 1 가지) 가 있 습 니 다. 이렇게 전달 식 이 있 습 니 다. 코드 는 다음 과 같 습 니 다.

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

좋은 웹페이지 즐겨찾기