- 1、题目描述:
-3、 设计思想:
详细操作流程看下图:
-4、视频讲解链接B站视频讲解
-5、代码:
c++版本:
class Solution { public: /** * 解码 * @param nums string字符串 数字串 * @return int整型 */ int solve(string nums) { // write code here if (nums[0] == '0') return 0; vector<int>dp(nums.size() + 10,0);//dp[i]的含义代表长度在i位置时有几种翻译办法 dp[0] = 1;//在第0个字符的时候只有一个字母所以只有一种翻译办法 for(int i = 1;i < nums.size();i ++){ if(nums[i] == '0'){ if(nums[i-1] == '1' || nums[i-1] == '2') { if(i == 1) dp[i] = 1;//特判字符串长度为2 else dp[i] = dp[i-2];//因为 10 20 这样的只有一种对应方案,所以此时dp[i]取决于dp[i-2] } } else if(nums[i - 1] == '1' || (nums[i - 1] == '2' && nums[i] >= '1' && nums[i] <= '6')){ /*11-26 抛去 20这样的组合 但是当i==1的时候如 12 21 这样有两种方案 当i>1时候dp[i] 取决于 dp[i-1] 和 dp[i-2]的和 */ if(i == 1) dp[i] = 2; else dp[i] = dp[i-1] + dp[i-2]; }else{ //>=27这样的组合 dp[i] = dp[i-1]; } } return dp[nums.size()-1]; } };
Java版本:
import java.util.*; public class Solution { /** * 解码 * @param nums string字符串 数字串 * @return int整型 */ public int solve (String nums) { // write code here if(nums.charAt(0) == '0') return 0; int [] dp = new int[nums.length()];//dp[i]的含义代表长度在i位置时有几种翻译办法 dp[0] = 1;//在第0个字符的时候只有一个字母所以只有一种翻译办法 for(int i = 1;i < nums.length();i ++){ if(nums.charAt(i) == '0'){ if(nums.charAt(i-1) == '1' || nums.charAt(i-1) == '2'){ if(i == 1) dp[i] = 1;//特判字符串长度为2 else dp[i] = dp[i-2];//因为 10 20 这样的只有一种对应方案,所以此时dp[i]取决于dp[i-2] } }else if(nums.charAt(i-1) == '1' || (nums.charAt(i-1) == '2' && nums.charAt(i) >= '1' && nums.charAt(i) <= '6')){ /*11-26 抛去 20这样的组合 但是当i==1的时候如 12 21 这样有两种方案 当i>1时候dp[i] 取决于 dp[i-1] 和 dp[i-2]的和 */ if(i == 1) dp[i] = 2; else dp[i] = dp[i-1] + dp[i-2]; }else{ //>=27这样的组合 dp[i] = dp[i-1]; } }return dp[nums.length() - 1]; } }
Python版本:
# # 解码 # @param nums string字符串 数字串 # @return int整型 # class Solution: def solve(self , nums ): # write code here if nums[0] == '0':return 0 dp=[0]*(len(nums)+10)#dp[i]的含义代表长度在i位置时有几种翻译办法 dp[0] = 1 #在第0个字符的时候只有一个字母所以只有一种翻译办法 for i in range(1,len(nums)): if nums[i] == '0': if nums[i-1] == '1' or nums[i-1] == '2': if i == 1: dp[i] = 1#特判字符串长度为2 else : dp[i] = dp[i-2]#因为 10 20 这样的只有一种对应方案,所以此时dp[i]取决于dp[i-2] elif nums[i-1] == '1' or (nums[i-1] == '2' and nums[i] >= '1' and nums[i] <= '6'): '''11-26 抛去 20这样的组合 但是当i==1的时候如 12 21 这样有两种方案 当i>1时候dp[i] 取决于 dp[i-1] 和 dp[i-2]的和 ''' if i == 1: dp[i] = 2 else: dp[i] = dp[i-1] + dp[i-2] else: #>=27这样的组合 dp[i] = dp[i-1] return dp[len(nums) - 1]