Today I Learned

오늘도 자바 코테 연습!

Decode Ways

Leetcode 91번 https://leetcode.com/problems/decode-ways/description/

문제

A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.

풀이 과정

• 주어진 문자열을 디코딩하여 가능한 방법의 수를 찾는 문제이다. 각 문자는 알파벳 'A'부터 'Z'까지의 알파벳에 매핑되어 있고, 디코딩은 주어진 문자열을 순회하면서 가능한 모든 조합을 찾아야 한다.

• 이 문제는 DP를 이용해 효율적으로 해결할 수 있다. 주어진 문자열의 각 위치에서 가능한 디코딩 방법의 수를 계산하고 저장하면서 전체 문자열을 탐색하는 방식으로 해결해보았다.

1. 먼저, 주어진 문자열이 null인지 또는 길이가 0인지, 또는 첫 번째 문자가 '0'인지 확인한다. 이 경우 디코딩이 불가능하므로 0을 반환하고, 아니면 DP를 위한 초기값을 설정한다.

2. 문자열의 길이만큼 반복하면서, 현재 인덱스에서 가능한 한 자리 숫자와 두 자리 숫자의 경우를 고려한다. 두 자리 숫자는 10~26, 한 자리 숫자는 1~9이다.

3. 각 위치에서 가능한 디코딩 방법의 수를 계산한다. 현재 위치의 한 자리 숫자가 1~9인 경우, 이전 위치의 디코딩 수를 더해주고, 두 자리 숫자가 10~26인 경우, 두 칸 앞의 디코딩 수를 더해준다.

4. 마지막 인덱스에 도달했을 때, 디코딩 수를 반환한다. 이 값은 가능한 디코딩 방법의 총 수이다.

Java 코드 & 결과

class Solution {
  public int numDecodings(String s) {
    if (s == null || s.isEmpty() || s.charAt(0) == '0') return 0;
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;

    for (int i = 2; i <= n; i++) {
      int one = Integer.parseInt(s.substring(i - 1, i));
      int two = Integer.parseInt(s.substring(i - 2, i));

      if (one >= 1 && one <= 9) {
        dp[i] += dp[i - 1];
      }

      if (two >= 10 && two <= 26) {
        dp[i] += dp[i - 2];
      }
    }

    return dp[n];
  }

}