問題連結: https://leetcode.com/problems/decode-ways/
一個包含字母 A-Z 的訊息可以加密成數字, 按照以下規則:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"而想要解碼加密訊息的話, 就要運用上述的規則倒回去找訊息
給予一個非空且裡面只包含數字的字串, 回傳總共有幾種方法可以解碼
範例 1.
Input: s = "226"
Output: 3
因為 "226" 可以拆成 "BZ" (2, 26), "VF" (22, 6), 或 "BBF" (2, 2, 6).
-------------------------------------------------------------------
範例 2.
Input: s = "0"
Output: 0, since there's no character that maps to 0.想法:
一時之間可能很難看出端倪, 我的第一個想法就是我們需要一個一個解碼, 我們必須先找出第一個字母, 才可以找下一個可能字母, 我們找到的第一個字母可能是由一位數或兩位數且小於等於26(Z)的數字組成, 在鎖定完字母後, 就會在剩餘還沒用過的數字之中, 重複剛剛找字母的步驟, 直到我們已把所有的數字湊完, 代表我們真的成功找到所有可以組成的訊息
👷讓我們來看我們前面所講的想法套用在s= “22678”
🔧Step 1. 找我們這個加密訊息的第一個字母, 我們發現第一個字母可以由2或22組成, 因為他們都是有效加密數字:
找完第一個字母後, 我們接下來分別就要依照我們決定的第一個字母, 來找如何解碼剩下的數字: “2678”(step 2–1) 跟 “678”(step 2–2)
我們先來看我們如何解碼 “2678”
🔧Step 2–1. 找第二個加密字母, 這次我們又發現下個字母可以由2 或26組成:
找完下一個解碼字母後, 我們又必須兵分兩路的找我們如何解碼“678”(step 2–1–1) 和 “78”(step 2–1–2)
如何解碼 “678”
🔧Step 2–1–1. 找下一個加密字母, 而這次只有6為可能的加密數字:
找到下一個字母後, 我們接下來就找我們如何解碼“78”(step 2–1–1.2)
如何解碼“78”
🔧Step 2–1–1.2. 找下一個加密字母, 而這次只有7為可能的加密數字:
找到下一個字母後, 我們接下來就找我們如何解碼“8”(step 2–1–1.3)
🔧Step 2–1–1.3. 找下一個加密字母, 而這次只有8為可能的加密數字:
找到下一個字母後, 我們接下來就找我們如何解碼“”(step 2–1–1.4)
如何解碼“”
🔧Step 2–1–1.4. 找下一個加密字母, 我們發現已經解完所有的加密數字了, 代表我們已經完成找完所有在"678"之中可能的加密訊息, 因此我們已完成在🔧step 2–1–1 所訂的目標, 成功找到一個解密訊息為*BBFGH (2, 2, 6, 7, 8)
💭現在我們則必須回去做完剛剛在 🔧step 2–1–2 還沒開始找的 “78”(而🔧step 2–1–2 需要幫忙解密"78"的過程其實跟我們在 🔧Step 2–1–1.2 ~ 2–1–1.4過程一樣, 都是幫忙找"78"), 找完後我們也找到另一個解密訊息為 *BZGH (2, 26, 7, 8)
💭找完在 🔧step 2–1–2 的目標訊息, 我們再次需要回去完成🔧step 2–2 還沒解碼的訊息 “678”, (🔧step 2–2 步驟也會同🔧step 2–1–1~2–1–1.4), 也會找到另一個解密訊息為 *VFGH (22, 6, 7, 8)
🚧我們總算完成剛剛分支出去還沒找完的所有解密步驟, 因此我們總共可以找到3個不同的解密訊息
程式邏輯:
而若我們把剛剛的想法寫成程式邏輯, 則會如下面程式碼所示
我們將會用一個helper method(參數需有字串s 及 開始位置indx)來負責回傳我們可以從現在位置indx開始的剩餘字串中, 找到多少不同的解密訊息
比如說我們一開始呼叫helper("123", 0), 代表我們是想要找"123"可以有幾種不同解密訊息
而在找到第一個字母可以由1或12組成後, 代表我們可以在"123"找到的解密訊息數量依照我們分別在"23"可以找到的解密訊息數量 加上 我們在"3"可以找到的解密訊息數量而決定
因此我們會呼叫 helper("123", 1) 跟 helper("123", 2) 來找他們可以找到的解密訊息數量來決定, 以此類推
在檢查現在字串的第一個數字(也就是在indx的數字)是有效的加密數字後(也就是非0), 代表答案等於我們在剩餘還沒解碼的字串可組成的解密訊息一樣, 因此把剩餘字串傳進helper method中, 而如果現在位置的數字又可以跟下一位數字組成有效的加密數字(≤26)的話, 代表我們也須考慮這個組合, 因此也把新的剩餘字串傳進helper method中
public int numDecodings(String s) {
return helper(s, 0);
}
public int helper(String s,int indx){
if(indx==s.length()) //we're done
return 1;
int curNum = s.charAt(indx)-'0';
if(curNum==0)
return 0;
int rst = helper(s,indx+1);
if(indx+1 < s.length())
{
int nextDigit = s.charAt(indx+1)-'0';
int twoNum = curNum*10+nextDigit;
if(twoNum<=26)
rst += helper(s, indx+2);
}
return rst;
}而上面的程式碼會在Leetcode上大部分的test cases中失敗, 原因是因為時間複雜度過長, 造成Time Limit Exceeded, 因為我們在每次都會想要或不要切, 若每次我們都可以兵分兩路, 那最終時間複雜度就是O(2^n), 就像我們在最一開始的例子, 我們重複去解密“678”, 然後跑了一整遍一樣的過程
而避免這種情況發生, 我們可以利用變數來紀錄我們解密過的字串們, 我決定用map來記錄我們找過的字串跟我們找到最後所得到它可以解密訊息的個數, 比如"01"就會是0, "11"可解成2個解密訊息
因為我們在呼叫helper method中會讓indx跑完整個字串甚至超出去, 而s.substring(n)在java中是空值, 我會先在map中先放空值代表解成1個解密訊息, 來代表當我們跑到這裡的時候, 代表你是成功的解完前面所有訊息了 (跟我們上面程式碼在indx==n的時候就回傳1同樣邏輯)
以下為1ms的程式碼, 贏過 94% —
public int numDecodings(String s) {
Map<String,Integer> visited = new HashMap<>();
visited.put("",1);
return helper(s, 0, visited);
}
public int helper(String s,int indx,Map<String,Integer> visited){
String substr = s.substring(indx);
if(visited.get(substr)!=null)
return visited.get(substr);
int curNum = s.charAt(indx)-'0';
if(curNum==0)
{
visited.put(substr,0);
return 0;
}
int rst = helper(s,indx+1, visited);
if(indx+1 < s.length())
{
int nextDigit = s.charAt(indx+1)-'0';
int twoNum = curNum*10+nextDigit;
if(twoNum<=26)
rst += helper(s,indx+2,visited);
}
visited.put(substr, rst);
return rst;
}我們也可以不要用遞迴的方式解這題, 我們改用一個整數陣列dp來輔助我們
因為這次我們會乖乖地從index =0慢慢地找可能性, 因此我們不可能在還沒到index i之前, 就找到我們在index i開始的字串 可以解出有多少個不同解密訊息, 因為我們應該是要好好利用我們在走到index i之前所遇過的字串所得到的資訊, 我們不再用map來記錄我們在從i開始之後的字串可得到多少個解密訊息
相反地, 我們現在改成用變數(陣列dp)來紀錄我們在這個位置之前所組成的字串有多少個解密方法, 因此dp[i]將代表我們在整個字串的前i個數字字串們可以組成幾個不同解密訊息 (也就是dp[2]就會代表我們在整個字串的頭兩個數字可以組成幾個不同訊息)
我們在每次計算dp[i]可組成的解密訊息的時候, 需考慮在第i個位置(也就是s.charAt(i-1), 因為index從0開始) 的數字的值以及他前一個數字的值
而套用這樣的跑法, 當input s = “22678”,
我們的dp陣列最後會像這樣 [1, 1, 2, 3, 3, 3] (dp[2]就代表"22"可以組成2個不同訊息)
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
for(int i=1;i<=n;i++)
{
int indx = i-1;
int curNum = s.charAt(indx) - '0';
if(curNum!=0)
dp[i] = dp[i-1];
if(i>1)
{
int prevDigit = s.charAt(indx-1) - '0';
if(prevDigit==0)
continue;
int twoNum = prevDigit*10 + curNum;
if(twoNum<=26)
dp[i] += dp[i-2];
}
}
return dp[n];
}從上述程式碼我們也可以看到,其實我們也每次都至多參考前兩個位置在dp陣列的值而已, 不太真的需要整個陣列, 因此我們也可以省去用整個陣列存值, 改成用兩個變數 prev2 來代表dp[i-2], prev來代表dp[i-1]
因此可得下面0ms 程式碼, 贏過100%的人 —
public int numDecodings(String s) {
int n = s.length();
if(n==1)
return s.charAt(0)=='0'?0:1;
int prev2 = 1;
int prev = s.charAt(0)=='0'?0:1;
for(int i=1;i<n;i++)
{
int curNum = s.charAt(i)-'0';
int rst = 0;
if(curNum!=0)
rst = prev;
int prevNum = s.charAt(i-1)-'0';
if(prevNum!=0)
{
int twoNum = prevNum*10 + curNum;
if(twoNum <= 26)
rst+= prev2;
}
prev2 = prev;
prev = rst;
}
return prev;
}
