decode_ways.md

🔥 Decode Ways 🔥 || Simple Fast and Easy || with Explanation

Solution - 1 Tabulation

class Solution {
  // Using Tabulation
  // Runtime: 522 ms, faster than 50.00% of Dart online submissions for Decode Ways.
// Memory Usage: 140.3 MB, less than 100.00% of Dart online submissions for Decode Ways.
  int numDecodings(String s) {
    // if the string is empty
    if (s.isEmpty) return 0;
    // the length of the list
    int n = s.length;
    // filling the range of the list
    List<int> dp = List.filled(n + 1, 0);
    // setting the length of to One
    dp[n] = 1;
    int t;
    // Checking if the current character is a zero. If it is, then it is setting the current
    // character to the next character. If the current character is not a zero, then it is checking if
    // the
    // current character is not equal to the length of the string minus one. If it is not equal to the
    // length
    // of the string minus one, then it is setting the current character to the current character times
    // ten
    // plus the next character. If the current character is greater than nine and less than
    // twenty-seven, then
    // setting the current character to the current character plus the next character plus two.
    for (int i = n - 1; i >= 0; i--) {
      t = s.codeUnitAt(i) - '0'.codeUnitAt(0);
      if (t > 0) {
        dp[i] = dp[i + 1];
        if (i != n - 1) t = 10 * t + s[i + 1].codeUnitAt(0) - '0'.codeUnitAt(0);
        if (t > 9 && t < 27) {
          dp[i] += dp[i + 2];
        }
      }
    }

    return dp[0];
  }
}

Solution - 2

class Solution {
// Runtime: 475 ms, faster than 50.00% of Dart online submissions for Decode Ways.
// Memory Usage: 140.6 MB, less than 100.00% of Dart online submissions for Decode Ways.
  // If the current character is 0, then the number of ways to decode is 0. Otherwise, the number of
  // ways to decode is the sum of the number of ways to decode the substring without the current
  // character and the number of ways to decode the substring without the current character and the
  // previous character
  //
  // Args:
  //   i (int): the index of the current character in the string
  //   s (String): the string to decode
  //   dp (List<int>): a list of integers, where dp[i] is the number of ways to decode the string
  // s[0..i]
  //
  // Returns:
  //   The number of ways to decode a string.
  int cal(int i, String s, List<int> dp) {
    if (i == -1 || i == 0) return 1;

    if (dp[i] != -1) return dp[i];
    int w1 = 0, w2 = 0;
    if (s.codeUnitAt(i) > '0'.codeUnitAt(0)) w1 = cal(i - 1, s, dp);
    if (s[i - 1] == '1' ||
        s[i - 1] == '2' && s.codeUnitAt(i) < '7'.codeUnitAt(0))
      w2 = cal(i - 2, s, dp);
    return dp[i] = w1 + w2;
  }

  /// It returns the number of ways to decode a string.
  ///
  /// Args:
  ///   s (String): the string to be decoded
  ///
  /// Returns:
  ///   The number of ways to decode the string.
  int numDecodings(String s) {
    int n = s.length;
    if (s == "0" && s[0] == '0') return 0;
    List<int> dp = List.filled(n + 1, -1);
    return cal(n - 1, s, dp);
  }
}

Solution - 3 Recursive

class Solution {
// Runtime: 466 ms, faster than 50.00% of Dart online submissions for Decode Ways.
// Memory Usage: 140.4 MB, less than 100.00% of Dart online submissions for Decode Ways.
  // A recursive function that returns the number of ways to decode a string.
  //
  // Args:
  //   index (int): the current index in the string
  //   s (String): the string to decode
  //   n (int): length of the string
  //   dp (List<int>): This is the list that will store the number of ways to decode the string.
  //
  // Returns:
  //   The number of ways to decode a string.
  int helper(int index, String s, int n, List<int> dp) {
    /// A recursive function that is checking if the index is greater than the length of the string. If it
    /// is, it returns 1. If the index is not greater than the length of the string, it checks if the index
    /// is equal to 0. If it is, it returns 0. If the index is not equal to 0, it checks if the index is
    /// not equal to -1. If it is not equal to -1, it returns the index. If the index is equal to -1, it
    /// takes the index and adds 1 to it. It then takes the index and adds
    if (index >= n) return 1;
    if (s[index] == '0') return 0;
    if (dp[index] != -1) return dp[index];
    int take = helper(index + 1, s, n, dp);
    int take2 = 0;

    /// Checking if the current index is less than n-1. If it is, then it is checking if the current
    /// index is 2 and the next index is less than or equal to 6. If it is, then it is setting take2 to
    /// the helper function with the index + 2. If the current index is 1, then it is setting take2 to
    /// the helper function with the index + 2.
    if (index < n - 1) {
      if (s[index] == '2' && s.codeUnitAt(index + 1) <= '6'.codeUnitAt(0))
        take2 = helper(index + 2, s, n, dp);
      else if (s[index] == '1') take2 = helper(index + 2, s, n, dp);
    }
    return dp[index] = take + take2;
  }

  int numDecodings(String s) {
    int n = s.length;

    /// Creating a list of size n and filling it with -1.
    List<int> dp = List.filled(n, -1);

    /// Returning the helper function with the index of 0, the string, the length of the string, and the
    /// list.
    return helper(0, s, n, dp);
  }
}

Solution - 4

class Solution {
  // > If the current character is a zero, then the number of ways to decode the string is the same as
  // the number of ways to decode the string without the current character. Otherwise, if the current
  // character is a one, then the number of ways to decode the string is the sum of the number of ways
  // to decode the string without the current character and the number of ways to decode the string
  // without the current character and the next character. Otherwise, if the current character is a two
  // and the next character is less than seven, then the number of ways to decode the string is the sum
  // of the number of ways to decode the string without the current character and the number of ways to
  // decode the string without the current character and the next character. Otherwise, if the current
  // character is a two and the next character is greater than or equal to seven, then the number of
  // ways to decode the string is the number of ways to decode the string without the current character.
  // Otherwise, the number
  //
  // Args:
  //   s (String): the string of digits
  //
  // Returns:
  //   The number of ways to decode the string.
  int optimization(String s) {
    int n = s.length;
    int next = 1, next2 = 0;

    for (int index = n - 1; index >= 0; index--) {
      int pick1 = 0, pick2 = 0;
      if (s[index] != '0') pick1 = next;
      if (index + 1 < n && s[index] != '0') {
        if (s[index].codeUnitAt(0) >= '3'.codeUnitAt(0))
          pick2 = 0;
        else if (s[index] == '2' &&
            s.codeUnitAt(index + 1) >= '7'.codeUnitAt(0))
          pick2 = 0;
        else
          pick2 = next2;
      }

      next2 = next;
      next = pick1 + pick2;
    }

    return next;
  }

  // It returns the number of ways to decode a string.
  //
  // Args:
  //   s (String): the string to decode
  //
  // Returns:
  //   The number of ways to decode a string.
  int numDecodings(String s) {
    return optimization(s);
  }
}

Solution - 5

class Solution {
  int numDecodings(String s) {
    Map<int, int> map = Map();
    return helper(s, 0, map);
  }

  int helper(String s, int index, Map<int, int> map) {
    if (map.containsKey(index)) {
      return map.keys.elementAt(index);
    }
    int len = s.length;

    if (index >= len) return 1;

    int numOfWays = 0;

    int firstNumberWithOneDigit = s.codeUnitAt(index);

    if (firstNumberWithOneDigit - '0'.codeUnitAt(0) > 0) {
      numOfWays += helper(s, index + 1, map);
    }

    if (index < len - 1) {
      String secondNumberWithTwoDigits = s.substring(index, index + 2);

      int value = parse(secondNumberWithTwoDigits);

      if (value <= 26 && value > 0) numOfWays += helper(s, index + 2, map);
    }
    map.forEach((key, value) {
      key = index;
      value = numOfWays;
    });
    return numOfWays;
  }

  int parse(String nums) {
    if (nums.isEmpty) return 0;

    if (nums.startsWith("0")) {
      return 0;
    }

    int result = 0;

    try {
      result = int.parse(nums);
    } catch (e) {
      return 0;
    }

    return result;
  }
}