LeetCode Summary
  • Introduction
  • DP, 动态规划类
    • Best Time to Buy and Sell Stock III 题解
    • Best Time to Buy and Sell Stock 题解
    • Climbing Stairs 题解
    • Decode Ways 题解
    • Distinct Subsequences 题解
    • Edit Distance 题解
    • Interleaving String 题解
    • Longest Palindromic Substring 题解
    • Maximum Product Subarray 题解
    • Maximum Subarray 题解
    • Minimum Path Sum 题解
    • Palindrome Partitioning 题解
    • Palindrome Partitioning II 题解
    • Scramble String 题解
    • Triangle 题解
    • Unique Binary Search Trees 题解
    • Unique Paths II 题解
    • Word Break 题解
    • Word Break II 题解
  • list, 链表相关
    • Add Two Numbers 题解
    • Convert Sorted List to Binary Search Tree 题解
    • Copy List with Random Pointer 题解
    • Insertion Sort List 题解
    • LRU Cache 题解
    • Linked List Cycle 题解
    • Linked List Cycle II 题解
    • Merge Two Sorted Lists 题解
    • Merge k Sorted Lists 题解
    • Partition List 题解
    • Remove Duplicates from Sorted List 题解
    • Remove Duplicates from Sorted List II 题解
    • Remove Nth Node From End of List 题解
    • Reorder List 题解
    • Reverse Linked List II 题解
    • Reverse Nodes in k-Group 题解
    • Rotate List 题解
    • Sort List 题解
    • Swap Nodes in Pairs 题解
  • binary tree, 二叉树相关
    • Balanced Binary Tree 题解
    • Binary Tree Inorder Traversal 题解
    • Binary Tree Level Order Traversal 题解
    • Binary Tree Level Order Traversal II 题解
    • Binary Tree Maximum Path Sum 题解
    • Binary Tree Postorder Traversal 题解
    • Binary Tree Preorder Traversal 题解
    • Binary Tree Zigzag Level Order Traversal 题解
    • Construct Binary Tree from Inorder and Postorder Traversal 题解
    • Construct Binary Tree from Preorder and Inorder Traversal 题解
    • Convert Sorted List to Binary Search Tree 题解
    • Flatten Binary Tree to Linked List 题解
    • Maximum Depth of Binary Tree 题解
    • Minimum Depth of Binary Tree 题解
    • Path Sum 题解
    • Path Sum II 题解
    • Populating Next Right Pointers in Each Node 题解
    • Populating Next Right Pointers in Each Node II 题解
    • Recover Binary Search Tree 题解
    • Same Tree 题解
    • Sum Root to Leaf Numbers 题解
    • Symmetric Tree 题解
    • Unique Binary Search Trees 题解
    • Unique Binary Search Trees II 题解
    • Validate Binary Search Tree 题解
  • sort, 排序相关
    • 3Sum Closest 题解
    • 3Sum 题解
    • 4Sum 题解
    • Insert Interval 题解
    • Longest Consecutive Sequence 题解
    • Merge Intervals 题解
    • Merge Sorted Array 题解
    • Remove Duplicates from Sorted Array 题解
    • Remove Duplicates from Sorted Array II 题解
    • Sort Colors 题解
    • Two Sum 题解
  • search, 搜索相关
    • First Missing Positive 题解
    • Find Minimum in Rotated Sorted Array 题解
    • Find Minimum in Rotated Sorted Array II 题解
    • Median of Two Sorted Arrays 题解
    • Search Insert Position 题解
    • Search a 2D Matrix 题解
    • Search for a Range 题解
    • Search in Rotated Sorted Array 题解
    • Search in Rotated Sorted Array II 题解
    • Single Number 题解
    • Single Number II 题解
  • math, 数学类相关
    • Add Binary 题解
    • Add Two Numbers 题解
    • Divide Two Integers 题解
    • Gray Code 题解
    • Integer to Roman 题解
    • Multiply Strings 题解
    • Palindrome Number 题解
    • Plus One 题解
    • [Pow(x, n) 题解](math/Pow(x,-n).md)
    • Reverse Integer 题解
    • Roman to Integer 题解
    • [Sqrt(x) 题解](math/Sqrt(x).md)
    • [String to Integer (atoi) 题解](math/String-to-Integer-(atoi).md)
    • Valid Number 题解
  • string, 字符串处理相关
    • Anagrams 题解
    • Count and Say 题解
    • Evaluate Reverse Polish Notation 题解
    • [Implement strStr() 题解](string/Implement-strStr().md)
    • Length of Last Word 题解
    • Longest Common Prefix 题解
    • Longest Palindromic Substring 题解
    • Longest Substring Without Repeating Characters 题解
    • Longest Valid Parentheses 题解
    • Minimum Window Substring 题解
    • Regular Expression Matching 题解
    • Reverse Words in a String 题解
    • Simplify Path 题解
    • Text Justification 题解
    • Valid Parentheses 题解
    • Wildcard Matching 题解
    • ZigZag Conversion 题解
  • combination and permutation, 排列组合相关
    • Combinations 题解
    • Combination Sum 题解
    • Combination Sum II 题解
    • Letter Combinations of a Phone Number 题解
    • Next Permutation 题解
    • Palindrome Partitioning 题解
    • Permutation Sequence 题解
    • Permutations 题解
    • Permutations II 题解
    • Subsets 题解
    • Subsets II 题解
    • Unique Paths 题解
  • matrix, 二维数组, 矩阵相关
    • Rotate Image 题解
    • Set Matrix Zeroes 题解
    • Spiral Matrix 题解
    • Spiral Matrix II 题解
    • Maximal Rectangle 题解
  • 回溯, BFS/DFS
    • Clone Graph 题解
    • Generate Parentheses 题解
    • N-Queens 题解
    • N-Queens II 题解
    • Restore IP Addresses 题解
    • Sudoku Solver 题解
    • Surrounded Regions 题解
    • Word Ladder 题解
    • Word Ladder II 题解
    • Word Search 题解
  • greedy, 贪心
    • Best Time to Buy and Sell Stock II 题解
    • Jump Game 题解
    • Jump Game II 题解
  • 其他
    • Candy 题解
    • Container With Most Water 题解
    • Gas Station 题解
    • Gray Code 题解
    • Max Points on a Line 题解
    • [Pascal's Triangle 题解](others/Pascal's-Triangle.md)
    • [Pascal's Triangle II 题解](others/Pascal's-Triangle-II.md)
    • Remove Element 题解
    • Trapping Rain Water 题解
Powered by GitBook
On this page

Was this helpful?

  1. DP, 动态规划类

Decode Ways 题解

PreviousClimbing Stairs 题解NextDistinct Subsequences 题解

Last updated 5 years ago

Was this helpful?

题目来源：

> A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2.

解题思路：

动态规划. dp[i] 表示 s[0:i-1]的结果.

  1. 若当前字符s[i-1]为0

    • 若前面的字符是1或2, 则这1或2必须得跟0结合, dp[i] = dp[i-2] eg: XXX(10)

    • 若前面的字符不是1或者2, 拼接不起来了，直接return 0.

  2. 当前字符不为0

    • 前面的字符为1 或者 2且当前字符为1-6. 即可分两种情况拆分, dp[i] = dp[i-2] + dp[i-1], eg: XXX16: (XXX)(16) + (XXX1)6

    • 其他, 只能自己跟自己一组了. dp[i] = dp[i-1] eg: (XXX3)6

还可以将下面的O(n)空间化简成常数空间～记录之前上一次结果 和 上上一次的结果，当前的结果由此获得。

    int numDecodings(string s) 
    {
        if( s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.length()+1, 0);
        dp[0] = 1; dp[1] = 1;
        for(int i = 2; i <= s.length(); i++)
        {
            if(s[i-1] == '0')
            {
                if(s[i-2] == '1' || s[i-2] == '2')
                    dp[i] = dp[i-2];
                else
                    return 0;
            }else if(s[i-2] == '1' || (s[i-2]=='2' && s[i-1] <= '6'))
                dp[i] = dp[i-2] + dp[i-1];
            else
                dp[i] = dp[i-1];
        }
        return dp[s.length()];
    }
Decode Ways