-
Notifications
You must be signed in to change notification settings - Fork 0
/
decode_ways.rs
152 lines (138 loc) · 4.3 KB
/
decode_ways.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
use std::collections::HashMap;
/// 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.
struct Solution;
impl Solution {
fn char_to_digit(c: char) -> i32 {
match c {
'0' => 0,
'1' => 1,
'2' => 2,
'3' => 3,
'4' => 4,
'5' => 5,
'6' => 6,
'7' => 7,
'8' => 8,
'9' => 9,
_ => 0,
}
}
fn worker(results: &mut HashMap<usize, i32>, nums: &Vec<i32>, index: usize) -> i32 {
let result;
let n = nums.len();
if index == n {
result = 1;
} else if results.contains_key(&index) {
result = results[&index];
} else {
let value = nums[index];
if value == 0 {
result = 0;
} else if value == 1 {
if index == n-1 {
result = 1;
} else {
let next = nums[index+1];
if next == 0 {
result = Self::worker(results, nums, index+2);
} else {
result = Self::worker(results, nums, index+1) +
Self::worker(results, nums, index+2);
}
}
} else if value == 2 {
if index == n-1 {
result = 1;
} else {
let next = nums[index+1];
if next == 0 {
result = Self::worker(results, nums, index+2);
} else if next > 6 {
result = Self::worker(results, nums, index+1);
} else {
result = Self::worker(results, nums, index+1) +
Self::worker(results, nums, index+2);
}
}
} else {
result = Self::worker(results, nums, index+1);
}
results.insert(index, result);
}
result
}
pub fn num_decodings(s: String) -> i32 {
let nums: Vec<i32> = s.chars().map(Self::char_to_digit).collect();
let mut results = HashMap::new();
Self::worker(&mut results, &nums, 0)
}
}
#[cfg(test)]
mod tests {
use super::Solution;
#[test]
fn example_1() {
let s = "12".to_string();
let result = Solution::num_decodings(s);
assert_eq!(result, 2);
}
#[test]
fn example_2() {
let s = "226".to_string();
let result = Solution::num_decodings(s);
assert_eq!(result, 3);
}
#[test]
fn example_3() {
let s = "06".to_string();
let result = Solution::num_decodings(s);
assert_eq!(result, 0);
}
}
// 1. Write down the problem ✓
//
// 2. Clarify the problem space
// ** Input: s: String of numbers
// ** Output: integer: number of ways to decode the string.
// s.len() >= 1 and <= 100
// s contains only digits and may contain leading zero(s).
//
// 3. Write down the test cases
// ** Input: s = "12"
// ** Output: 2 ("12" could be "AB" or "L")
//
// ** Input: s = "226"
// ** Output: 3 ("226" could be "BBF", "BZ", or "VF")
//
// ** Input: s = "06"
// ** Output: 0
//
// 4. Describe and write down the algorithm
// Convert s to Vec<i32>
// Start with index = 0
// Dynamic programming problem with overlapping subproblems.
// If the current index only has one option, then the result is the result of subproblem.
// If it has more than one option, then the result is the combination of its subproblems.
// Time complexity: O(n)
// Space complexity: O(n)
//
//