91. Decode Ways

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).

---
Time - O(2 ^ N) - 2 branching at each recursive call - pure DFS
Time - O(N) - each index is visited only once - memoized
---

	class Solution {
	public int numDecodings(String s) {
	Integer[] memo = new Integer[s.length()];
	return dfs(s, 0, memo);
	}

	private int dfs(String s, int i, Integer[] memo) {
	if (i == s.length()) {
	return 1;
	}

	if (memo[i] != null) {
	return memo[i];
	}
	int ans = 0;

	int one = s.charAt(i) - '0';
	if (one > 0) {
	ans += dfs(s, i + 1, memo);

	if (i + 1 < s.length()) {
	int two = s.charAt(i + 1) - '0';
	int next = one * 10 + two;

	if (next <= 26) {
	ans += dfs(s, i + 2, memo);
	}
	}
	}
	memo[i] = ans;
	return ans;
	}
	}

	class Solution {
	public int numDecodings(String s) {
	// Number of ways to decode strins starting at index
	int[] ways = new int[s.length()];
	Arrays.fill(ways, -1);

	dfs(s, 0, ways);

	return ways[0];
	}

	private int dfs(String s, int i, int[] ways) {
	// If already explored, return that
	if (i < s.length() && ways[i] != -1) {
	return ways[i];
	}

	if (i >= s.length()) {
	return i == s.length() ? 1 : 0;
	}

	int ans = 0;
	if (isValid(s, i, i)) {
	ans += dfs(s, i + 1, ways);
	}

	if (isValid(s, i, i + 1)) {
	ans += dfs(s, i + 2, ways);
	}

	ways[i] = ans;

	return ans;
	}

	private boolean isValid(String s, int start, int end) {
	int digit1 = s.charAt(start) - '0';
	// Skip leading zeros
	if (digit1 == 0) {
	return false;
	}
	// All single digits except 0 are valid
	if (end - start == 0) {
	return true;
	}
	// Ended string, invalid
	if (end == s.length()) {
	return false;
	}

	int digit2 = s.charAt(end) - '0';
	int num = digit1 * 10 + digit2;

	return num <= 26;
	}
	}

	class Solution {
	public int numDecodings(String s) {
	return dfs(s, 0);
	}

	private int dfs(String s, int i) {
	// terminate recursion
	if (i >= s.length()) {
	return i == s.length() ? 1 : 0;
	}

	int ans = 0;
	if (isValid(s, i, i)) {
	ans += dfs(s, i + 1);
	}

	if (isValid(s, i, i + 1)) {
	ans += dfs(s, i + 2);
	}

	return ans;
	}

	private boolean isValid(String s, int start, int end) {
	int digit1 = s.charAt(start) - '0';
	// Skip leading zeros
	if (digit1 == 0) {
	return false;
	}
	// All single digits except 0 are valid
	if (end - start == 0) {
	return true;
	}
	// Ended string, invalid
	if (end == s.length()) {
	return false;
	}

	int digit2 = s.charAt(end) - '0';
	int num = digit1 * 10 + digit2;

	return num <= 26;
	}
	}

SWE Interview preparation