【每日演算法Day 86】面試經典題：把數字翻譯成字元串

• 2020 年 4 月 2 日
• 筆記

題目鏈接

LeetCode 面試題46. 把數字翻譯成字元串[1]

題目描述

給定一個數字，我們按照如下規則把它翻譯為字元串：0 翻譯成 「a」 ，1 翻譯成 「b」，……，11 翻譯成 「l」，……，25 翻譯成 「z」。一個數字可能有多個翻譯。請編程實現一個函數，用來計算一個數字有多少種不同的翻譯方法。

示例1

輸入：  12258  輸出:  5  解釋：  12258有5種不同的翻譯，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

說明：

題解

顯然這題就是個動態規劃問題，我們令 表示 到第 位為止表示的方法數。

那麼我們觀察 的第 位和第 位，也就是最後兩位，記為 。如果 ，那麼就可以把這兩位合併成一個字母表示，同時也可以分成兩個字母表示，所以 。但是如果 ，那就只能分成兩個字母來表示了，所以 。那如果 會怎麼樣呢？那說明最後兩位是 的形式，這種形式沒有辦法用一個字母表示，所以只能分成兩個字母表示，所以 。

綜上，如果 ，就有 ；否則的話就有 。

當然上面這是把 拆成了數字形式的字元串來做的，其實這題也可以直接用遞歸，這樣都不用轉變成字元串形式了。

我們直接令 表示數字 的方法數。那麼最後兩位結果就是 ，那麼如果 ，就有 ；否則的話就有 。遞歸的終止條件就是，如果 ，那麼只有一種表示方法。

當然這裡遞歸有重複計算，可以採用記憶化搜索，但是因為複雜度太低了，沒有必要。

時間複雜度為 ，也就是 的位數。

程式碼

c++

class Solution {  public:      int translateNum(int num) {          if (num < 10) return 1;          int res = translateNum(num/10), last = num%100;          if (10 <= last && last <= 25) res += translateNum(num/100);          return res;      }  };

python

class Solution:      def translateNum(self, num: int) -> int:          if num < 10: return 1          res, last = self.translateNum(num//10), num%100          if 10<=last<=25: res += self.translateNum(num//100)          return res

參考資料

[1]

LeetCode 面試題46. 把數字翻譯成字元串: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

作者簡介：godweiyang，知乎同名，華東師範大學電腦系碩士在讀，方向自然語言處理與深度學習。喜歡與人分享技術與知識，期待與你的進一步交流~