[LeetCode] 91. Decode Ways
Problem
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.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Constraints:
1 <= s.length <= 100scontains only digits and may contain leading zero(s).
Solution
class Solution {
public int numDecodings(String s) {
int[] arr = new int[s.length() + 1];
arr[0] = 1;
arr[1] = s.charAt(0) != '0' ? 1 : 0;
for (int i = 2; i <= s.length(); i++) {
int cur = Integer.valueOf(s.substring(i - 1, i));
if (1 <= cur && cur <= 9)
arr[i] += arr[i - 1];
int prev = Integer.valueOf(s.substring(i - 2, i));
if (10 <= prev && prev <= 26)
arr[i] += arr[i - 2];
} return arr[arr.length - 1];
}
}
앞에서 부터 잘라가면서 경우의 수를 누적함. 1자리만 잘랐을 때 전체 문자열의 경우의 수 + 2자리까지 잘랐을 때 전체 문자열의 경우의 수. 본인의 자리의 경우의 수 + 본인 앞의 자리까지 경우의 수.(본인 앞 자리를 확인해야 함) 2자리를 잘랐을 때가 제일 중요함. 1자리씩 자르면 경우의 수는 1밖에 안나옴. 해당 자리까지 잘랐을 때 경우의 수 + 해당 자리와 앞자리를 더해서 잘랐을 때의 경우의 수. 누적. 문자를 한 자리로만 자르면 경우의 수는 한 가지 밖에 나오지 않는다. 이 때, 첫 번째 문자는 한 자리밖에 없으므로 0이거나 1 ~ 9사이거나 둘 중에 따라
Explanation
- 문자를 한 자리로만 묶을 수 있다면, 경우의 수는 한 가지 밖에 나오지 않는다. 따라서 문제를 해결하기 위해서는 다음과 같이 문자를 2개로 묶었을 때의 경우의 수를 더해주어야 한다.
"1" -> 1(1가지) = 총 1가지 "12" -> 1/2(1가지) + 12(1가지) = 총 2가지 "123" -> 1/2/3(1가지) + 1/23, 12/3(2가지) = 총 3가지 "1234" -> 1/2/3/4(1가지) + 1/2/34, 1/23/4, 12/3/4, 12/34(4가지) = 총 5가지 "12345" -> 1/2/3/4/5(1가지) + 1/2/3/45, 1/2/34/5, 1/23/4/5, 12/3/4/5, 1/23/45, 12/3/45, 12/34/5(7가지) = 총 8가지 - 위의 예시에서 알 수 있는 것은
길이가 n인 문자열의 Decode경우의 수는길이가 n - 1인 문자열과길이가 n - 2인 문자열의 Decode경우의 수를 합한 것과 같다는 것이다. - 이는 길이가 n인 문자열의 Decode경우의 수를 구하려면, 길이가 1인 문자열의 Decode경우의 수, 길이가 2인 문자열의 Decode경우의 수… 길이가 n - 2인 문자열의 Decode경우의 수, 길이가 n - 1인 문자열의 경우의 수를 구해야 한다는 의미가 된다. 따라서 길이가 n - 1인 문자열의 Decode경우의 수와 길이가 n - 2인 문자열의 Decode경우의 수를 저장할 두 개의 공간이 필요하다.
- 길이가 1인 문자열의 Decode경우의 수는 문자열이 0이 아니라면 1가지 밖에 없으므로, 길이가 2인 문자열의 Decode경우의 수부터 구하기 위해 길이가 3인 배열을 선언한다.
int[] arr = new int[3]; - 배열의 인덱스는 문자열을 인덱스만큼 잘랐을 때의 Decode경우의 수를 나타낸다.
- 문자열의 첫 문자가 0이 아니면 1가지 경우의 수를 가지므로 이를 반영하여 인덱스 1의 배열 요소를 할당해준다.
arr[1] = s.charAt(0) != '0' ? 1 : 0; - 문자열의 두 번째 문자가 Decode가능하다면 인덱스 2의 배열 요소에 인덱스 1의 배열 요소의 값을 할당하면 된다.
- 첫 번째 문자와 두 번째 문자로 이루어진 문자열이 Decode가능하다면 경우의 수가 1추가 되어야 하는데 이 값을 인덱스 0의 배열 요소에서 가져오도록 배열의 첫 요소에 1을 할당하고 인덱스 2의 배열 요소에 인덱스 0의 배열 요소를 추가해준다.
arr[0] = 1; int cur = Integer.valueOf(s.substring(1, 2)); if (1 <= cur && cur <= 9) arr[2] += arr[1]; int prev = Integer.valueOf(s.substring(0, 2)); if (10 <= prev && prev <= 26) arr[2] += arr[0]; - 문자열의 길이가 더 길 경우에는 더 긴 배열이 필요하고, 또한 배열의 요소를 채워나가는 반복이 필요하므로 for반복문을 작성한다.
int[] arr = new int[s.length() + 1]; arr[0] = 1; arr[1] = s.charAt(0) != '0' ? 1 : 0; for (int i = 2; i <= s.length(); i++) { int cur = Integer.valueOf(s.substring(i - 1, i)); if (1 <= cur && cur <= 9) arr[i] += arr[i - 1]; int prev = Integer.valueOf(s.substring(i - 2, i)); if (10 <= prev && prev <= 26) arr[i] += arr[i - 2]; } - 문자열의 길이가 n일 때 Decode경우의 수는 배열의 마지막 요소가 되므로 배열의 마지막 요소를 반환한다.
return arr[arr.length - 1];
Leave a comment