leetcode136，Leetcode639. Decode Ways II

2023-12-25 阅读 32 评论 0

摘要：題目： A message containing letters from A-Z is being encoded to numbers using the following mapping way: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Beyond that, now the encoded string can also contain the character ‘*’, whic

題目：

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

leetcode136。Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod $10^9 + 7$ .

代碼（c++）：

這個代碼有bug，具體出錯在求余上。目前還沒有解決。

class Solution {
public:int numDecodings(string s) {long long int decode1, decode2;if(s[0] == '0') return 0;else if(s[0] == '*') decode1 = 9;else decode1 = 1;if(s.length() == 1) {return decode1;}if(s[0] == '1'){if(s[1] == '0') decode2 = 1;else if(s[1] == '*') decode2 = decode1*9 + 9;else decode2 = 2;}else if(s[0] == '2'){if(s[1] == '0') decode2 = 1;else if(s[1] == '*') decode2 = decode1*9 + 6;else if(s[1]-'0' <= 6) decode2 = 2;else decode2 = 1;}else if(s[0] == '*'){if(s[1] == '0') decode2 = 2;else if(s[1] == '*') decode2 = decode1*9 + 15;else if(s[1]-'0' <= 6) decode2 = decode1 + 2;else decode2 = decode1 + 1;}else {if(s[1] == '0') return 0;else if(s[1] == '*') decode2 = decode1*9;else decode2 = decode1;}for(int i = 2; i < s.length(); i++){long long int temp = decode2;if(s[i-1] == '1'){if(s[i] == '0') decode2 = decode1;else if(s[i] == '*') decode2 = decode2*9 + decode1*9;else decode2 = decode1 + decode2;}else if(s[i-1] == '2'){if(s[i] == '0') decode2 = decode1;else if(s[i] == '*') decode2 = decode2*9 + decode1*6;else if(s[i]-'0' <= 6) decode2 = decode1 + decode2;else decode2 = decode1;}else if(s[i-1] == '*'){if(s[i] == '0') decode2 = decode1*2;else if(s[i] == '*') decode2 = decode2*9 + decode1*15;else if(s[i]-'0' <= 6) decode2 = decode2 + decode1*2;else decode2 = decode2 + decode1;}else {if(s[i] == '0') return 0;else if(s[i] == '*') decode2 = decode2*9;}decode1 = temp;decode2 = decode2 % 1000000007;}return decode2;}
};

LeetCode，接下來的解決方法是leetcode提供的：

一、帶記憶的遞歸

用一個數組memo來保存子序列的結果，遞歸求結果。主要的難點就是遞推的關系式。時間復雜度 $O (n)$ ，空間復雜度 $O (n)$ 。

public class Solution {int M = 1000000007;public int numDecodings(String s) {Integer[] memo=new Integer[s.length()];return ways(s, s.length() - 1,memo);}public int ways(String s, int i,Integer[] memo) {if (i < 0)return 1;if(memo[i]!=null)return memo[i];if (s.charAt(i) == '*') {long res = 9 * ways(s, i - 1,memo);if (i > 0 && s.charAt(i - 1) == '1')res = (res + 9 * ways(s, i - 2,memo)) % M;else if (i > 0 && s.charAt(i - 1) == '2')res = (res + 6 * ways(s, i - 2,memo)) % M;else if (i > 0 && s.charAt(i - 1) == '*')res = (res + 15 * ways(s, i - 2,memo)) % M;memo[i]=(int)res;return memo[i];}long res = s.charAt(i) != '0' ? ways(s, i - 1,memo) : 0;if (i > 0 && s.charAt(i - 1) == '1')res = (res + ways(s, i - 2,memo)) % M;else if (i > 0 && s.charAt(i - 1) == '2' && s.charAt(i) <= '6')res = (res + ways(s, i - 2,memo)) % M;else if (i > 0 && s.charAt(i - 1) == '*')res = (res + (s.charAt(i)<='6'?2:1) * ways(s, i - 2,memo)) % M;memo[i]= (int)res;return memo[i];}
}

二、動態規劃

和我的思路大致相同，該答案計算最優解的思路更加清晰簡潔。時間復雜度 $O (n)$ ，空間復雜度 $O (n)$ ；

public class Solution {int M = 1000000007;public int numDecodings(String s) {long[] dp = new long[s.length() + 1];dp[0] = 1;dp[1] = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1;for (int i = 1; i < s.length(); i++) {if (s.charAt(i) == '*') {dp[i + 1] = 9 * dp[i];if (s.charAt(i - 1) == '1')dp[i + 1] = (dp[i + 1] + 9 * dp[i - 1]) % M;else if (s.charAt(i - 1) == '2')dp[i + 1] = (dp[i + 1] + 6 * dp[i - 1]) % M;else if (s.charAt(i - 1) == '*')dp[i + 1] = (dp[i + 1] + 15 * dp[i - 1]) % M;} else {dp[i + 1] = s.charAt(i) != '0' ? dp[i] : 0;if (s.charAt(i - 1) == '1')dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M;else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M;else if (s.charAt(i - 1) == '*')dp[i + 1] = (dp[i + 1] + (s.charAt(i) <= '6' ? 2 : 1) * dp[i - 1]) % M;}}return (int) dp[s.length()];}
}

三、常數空間的動態規劃

leetcode323，這個的思路和我的思路是一致的，因為最優子問題的解并不需要保存所有，當前長度為n的子問題的解 $F (n)$ 只與 $F (n ? 1)$ 和 $F (n ? 2)$ 有關。

public class Solution {int M = 1000000007;public int numDecodings(String s) {long first = 1, second = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1;for (int i = 1; i < s.length(); i++) {long temp = second;if (s.charAt(i) == '*') {second = 9 * second;if (s.charAt(i - 1) == '1')second = (second + 9 * first) % M;else if (s.charAt(i - 1) == '2')second = (second + 6 * first) % M;else if (s.charAt(i - 1) == '*')second = (second + 15 * first) % M;} else {second = s.charAt(i) != '0' ? second : 0;if (s.charAt(i - 1) == '1')second = (second + first) % M;else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')second = (second + first) % M;else if (s.charAt(i - 1) == '*')second = (second + (s.charAt(i) <= '6' ? 2 : 1) * first) % M;}first = temp;}return (int) second;}
}

c++版代碼

class Solution {
public:int numDecodings(string s) {int M = 1000000007;long long int first = 1, second = s[0] == '*' ? 9 : s[0] == '0' ? 0 : 1;for (int i = 1; i < s.length(); i++) {long long int temp = second;if (s[i] == '*') {second = 9 * second;if(s[i - 1] == '1') second = (second + 9 * first) % M;else if(s[i - 1] == '2') second = (second + 6 * first) % M;else if(s[i - 1] == '*') second = (second + 15 * first) % M;}else {second = s[i] != '0' ? second : 0;if(s[i - 1] == '1') second = (second + first) % M;else if(s[i - 1] == '2' && s[i] <= '6') second = (second + first) % M;else if(s[i - 1] == '*') second = (second + (s[i] <= '6' ? 2 : 1) * first) % M;}first = temp;}return (int)second;}
};