LeetCode seems to be as popular as YouTube

-
I was shocked when I looked at this problem on LeetCode today: https://leetcode.com/problems/decode-ways/description/

We'll get back to the problem soon, but the shocking part wasn't so much that this is a medium-complexity dynamic programming problem, but rather it was this:


Unless the site is lying or there is a bug somewhere, there have been over 1,000,000 submissions to this problem!
You see numbers of this magnitude on popular Instagram posts or popular silly (or professional) YouTube videos.
But I'd never have imagined that an algorithm problem that if you try brute-force times out hence you want to use dynamic programming (memoization) to cut down the execution time to O(n)-time at the cost of an extra space of O(n) space complexity would ever be something popular!

Code is everything, it is everywhere, algorithms are the heart of this world and it is amazing to be leaving in such a revolutionary era where in the past 100 years everything has been transformed due to algorithms and mathematics!!!

Alright, the solution to the problem (copied/pasted below) is down below, DP. Cheers, Boris.
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).


public int NumDecodings(string s)
{
 if (String.IsNullOrEmpty(s)) return 0;

 int[] dp = new int[s.Length];

 //Base
 dp[0] = (s[0] >= '1' && s[0] <= '9') ? 1 : 0;
 if (dp[0] == 0) return 0;

 //Construction
 for (int i = 1; i < s.Length; i++)
 {
  if (s[i] >= '1' && s[i] <= '9') dp[i] = dp[i - 1]; //Only one option

  string p = s.Substring(i - 1, 2);
  int n = Int32.Parse(p);

  if (!p.StartsWith("0") && n >= 1 && n <= 26)
  {
   if (i - 2 < 0) dp[i]++; //One more
   else dp[i] += dp[i - 2]; //Adding the option from two cells back
  }    
 }

 return dp[dp.Length - 1];
}

Comments

  1. TarasJanuary 27, 2019 at 2:44 PM

    Great solution, Boris! It can be further optimized by not using a dp array, since only 2 states are used, removing `if`s from the loop as they cause pipeline stalls, and not using Substring/Parse which are also not free.

    Once implemented these ideas look like

    class Solution {
    public:
    int numDecodings(const string& s) {
    if (s.empty()) return 0;
    if (s.size() == 1) return s[0] != '0';
    int n_2 = s.back() != '0';
    int n_1 = (s[s.size()-2] != '0') * n_2 + (s[s.size()-2] == '1' || s[s.size()-2] == '2' && s.back() <= '6');
    for (int i = s.size()-3; i >= 0; --i) {
    int num = (s[i] > '0') * n_1 + (s[i] == '1' || s[i] == '2' && s[i+1] <= '6') * n_2;
    n_2 = n_1;
    n_1 = num;
    }
    return n_1;
    }
    };

    https://gist.github.com/ttsugriy/f7d2b2671a90d228e53e9b7358f32253

    I've also posted my poor explanation on https://leetcode.com/problems/decode-ways/discuss/227291/O(N)-time-O(1)-space-DP-solution-in-C%2B%2B-(0ms)

    ReplyDelete
  2. TarasJanuary 27, 2019 at 2:45 PM

    P.S.: this is indeed great that programming challenges are getting so popular. I guess a lot of people are prepping for interviews :)

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more