資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給定包含隱藏字元的數字序列的可能解碼數
給定包含隱藏字元的數字序列的可能解碼數是字串解碼領域中一個引人入勝的問題。在本教程中，我們將深入探討解碼包含由星號（'*'）表示的隱藏字元的數字序列的挑戰。
我們的任務是確定這些隱藏字元可以解碼的方式數量，同時考慮到從 A 到 Z 的字母到數字 1 到 26 的特定對映。我們將使用 C++ 程式語言和動態規劃技術的強大功能提供一個有效的解決方案。
透過採用自底向上的方法，我們開發了一個 C++ 程式，該程式遍歷數字序列，分析隱藏字元，並計算可能的解碼總數。在整個教程中，我們將討論問題陳述，說明解決方案演算法，並提供 C++ 中的分步實現，使讀者能夠理解和將這種解碼技術應用到他們自己的場景中。所以讓我們開始吧！
問題陳述
考慮一個由數字和特殊字元 '*' 組成的字串 'S'，它表示一個隱藏字元。任務是找到該字串的可能解碼數，同時考慮到隱藏字元。
最終結果應以 '10^9 + 7' 為模返回，以處理可能的大量解碼。
字串中的每個字元都可以根據給定的對映對映到相應的數字，其中 'A' 表示 "1"，'B' 表示 "2"，依此類推，直到 'Z' 表示 "26"。需要注意的是，表示大於 26 的數字的字元不被視為有效對映（例如，'J' 不對映到 10）。
目標是計算有效解碼的總數，同時考慮由 '*' 表示的隱藏字元的存在。讓我們透過示例進一步探討這個問題。
示例 1
輸入
String: "*"
輸出
Number of possible decodings: 9
解釋：在這個例子中，輸入字串是 ""，它表示一個隱藏字元。隱藏字元可以被替換為 1 到 9 之間的任何數字。每個數字對應於從 'A' 到 'I' 的唯一字母。因此，編碼訊息有可能表示以下任何編碼訊息："1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9"。每個編碼訊息都可以解碼成相應的字母 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I"。因此，考慮到隱藏字元的所有可能替換，總共有 9 種唯一的方式來解碼字串 ""。
示例 2
輸入
String: "1*"
輸出
Number of possible decodings: 18
解釋：在這個例子中，輸入字串是 "1*"。由 '*' 表示的隱藏字元可以被替換為 0 到 9 之間的任何數字。這導致該字串有多個可能的編碼訊息，例如 "10"、"11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"。每個編碼訊息都有 2 種唯一的方式可以解碼。例如，編碼訊息 "11" 可以解碼為 "AA" 或 "K"。因此，第一個數字總共有 9 種可能性，並且每種可能性都有 2 種解碼選項，導致總共有 9 * 2 = 18 種唯一的方式來解碼字串 "1*"。
在這兩個例子中，輸出表示給定輸入字串的有效解碼總數，同時考慮了隱藏字元的所有可能替換。
演算法
1. 以給定的數字序列作為輸入。
2. 初始化大小為 'n + 1' 的動態規劃表 'dp'，其中 'n' 是序列的長度。
3. 設定 'dp[0] = 1'，因為只有一種方法可以解碼空序列。
4. 檢查序列的第一個數字
如果它是 '0'，則返回 0，因為它本身無法解碼。
如果它是 '*'，則設定 'dp[1] = 9'，因為它可以表示 1 到 9 之間的任何數字。
否則，設定 'dp[1] = 1'，因為第一個數字可以單獨解碼。
5. 從第二個數字迭代到序列的末尾
如果當前數字是 '*'
將計數乘以 9 以考慮它可能是 1 到 9 之間的任何數字的可能性。
檢查前一個數字以計算其他組合
如果前一個數字是 '1'，則將 '9 * dp[i - 2]' 新增到計數中。
如果前一個數字是 '2'，則將 '6 * dp[i - 2]' 新增到計數中。
如果前一個數字是 '*'，則將 '15 * dp[i - 2]' 新增到計數中（考慮所有可能性）。
否則（當前數字不是 '*'）
如果當前數字不是 '0'，則設定 'dp[i] = dp[i - 1]'，因為它可以單獨解碼。
檢查前一個數字以計算其他組合
如果前一個數字是 '1'，則將 'dp[i - 2]' 新增到計數中。
如果前一個數字是 '2' 且當前數字小於或等於 '6'，則將 'dp[i - 2]' 新增到計數中。
如果前一個數字是 '*'，則將 '(2 或 1) * dp[i - 2]' 新增到計數中，具體取決於當前數字的值。
6. 返回 'dp[n]'，它表示給定序列的可能解碼數。
該演算法使用動態規劃迭代地構建解碼計數，同時考慮每個數字的約束和可能性。
示例
使用 C++ 實現上述演算法
下面的 C++ 程式根據一組解碼規則計算解碼給定字串的方式數量。它使用自底向上的動態規劃方法有效地計算字串中每個位置的解碼數量。該程式遍歷字串的字元，應用解碼規則，並將結果儲存在動態規劃陣列中。最後，它返回整個字串的可能解碼數量。
輸入
"1*"
輸出
Number of possible decodings: 18
示例
#include <iostream>
#include <vector>
const int MOD = 1000000007;
int countDecodings(const std::string& sequence) {
int n = sequence.length();
// Base cases
if (n == 0 || sequence[0] == '0') {
return 0;
}
// Initialize the dynamic programming table
std::vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = (sequence[0] != '0');
// Fill the dynamic programming table
for (int i = 2; i <= n; ++i) {
// If the current digit is '*', multiply the count by 9
if (sequence[i - 1] == '*') {
dp[i] = (9 * dp[i - 1]) % MOD;
// Consider the previous digit for additional combinations
if (sequence[i - 2] == '1') {
dp[i] = (dp[i] + 9 * dp[i - 2]) % MOD;
} else if (sequence[i - 2] == '2') {
dp[i] = (dp[i] + 6 * dp[i - 2]) % MOD;
} else if (sequence[i - 2] == '*') {
dp[i] = (dp[i] + 15 * dp[i - 2]) % MOD;
}
} else {
// If the current digit is not '*', check if it is valid on its own
dp[i] = (sequence[i - 1] != '0' ? dp[i - 1] : 0);
// Consider the previous digit for additional combinations
if (sequence[i - 2] == '1') {
dp[i] = (dp[i] + dp[i - 2]) % MOD;
} else if (sequence[i - 2] == '2' && sequence[i - 1] <= '6') {
dp[i] = (dp[i] + dp[i - 2]) % MOD;
} else if (sequence[i - 2] == '*') {
dp[i] = (dp[i] + (sequence[i - 1] <= '6' ? 2 : 1) * dp[i - 2]) % MOD;
}
}
}
return dp[n];
}
int main() {
std::string sequence = "1*";
int numDecodings = countDecodings(sequence);
std::cout << "Number of possible decodings: " << numDecodings << std::endl;
return 0;
}
輸出
Number of possible decodings: 18
結論
總而言之，我們探討了包含隱藏字元的數字序列的解碼問題，並使用 C++ 和動態規劃提出了一個有效的解決方案。透過利用 C++ 程式語言的強大功能並採用自底向上的方法，我們開發了一個程式，該程式有效地計算此類序列的可能解碼數。我們的解決方案考慮了字母到數字的特定對映，並處理了由星號表示的隱藏字元的存在。透過遵循分步實現並理解底層演算法，讀者現在可以在他們自己的專案中解決類似的解碼挑戰。
249 次檢視
