91. Decode Ways

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    private int RecursiveWithMemo(int index, string s) {
        if (memo.ContainsKey(index)) {
            return memo[index];
        }
        if (index == s.Length) {
            return 1;
        }
        if (s[index] == '0') {
            return 0;
        }
        if (index == s.Length - 1) {
            return 1;
        }
        int ans = RecursiveWithMemo(index + 1, s);
        if (int.Parse(s.Substring(index, 2)) <= 26) {
            ans += RecursiveWithMemo(index + 2, s);
        }
        memo[index] = ans;
        return ans;
    }
    public int NumDecodings(string s) {
        return RecursiveWithMemo(0, s);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<int, int> memo = new unordered_map<int, int>();
    private int RecursiveWithMemo(int index, string s) {
        if (memo.count(index)) {
            return memo[index];
        }
        if (index == s.size()) {
            return 1;
        }
        if (s[index] == '0') {
            return 0;
        }
        if (index == s.size() - 1) {
            return 1;
        }
        int ans = RecursiveWithMemo(index + 1, s);
        if (int.Parse(s.Substring(index, 2)) <= 26) {
            ans += RecursiveWithMemo(index + 2, s);
        }
        memo[index] = ans;
        return ans;
    }
    public int NumDecodings(string s) {
        return RecursiveWithMemo(0, s);
    }
}

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();

    public int numDecodings(String s) {
        return recursiveWithMemo(0, s);
    }

    private int recursiveWithMemo(int index, String str) {
        if (memo.containsKey(index)) {
            return memo.get(index);
        }

        if (index == str.length()) {
            return 1;
        }

        if (str.charAt(index) == '0') {
            return 0;
        }

        if (index == str.length() - 1) {
            return 1;
        }

        int ans = recursiveWithMemo(index + 1, str);
        if (Integer.parseInt(str.substring(index, index + 2)) <= 26) {
            ans += recursiveWithMemo(index + 2, str);
        }

        memo.put(index, ans);

        return ans;
    }
}

var numDecodings = function (s) {
    let memo = new Object();
    return recursiveWithMemo(0, s, memo);
};
const recursiveWithMemo = (index, str, memo) => {
    if (memo.hasOwnProperty(index)) {
        return memo[index];
    }
    if (index == str.length) {
        return 1;
    }
    if (str.charAt(index) == "0") {
        return 0;
    }
    if (index == str.length - 1) {
        return 1;
    }
    let ans = recursiveWithMemo(index + 1, str, memo);
    if (parseInt(str.substring(index, index + 2)) <= 26) {
        ans += recursiveWithMemo(index + 2, str, memo);
    }
    memo[index] = ans;
    return ans;
};

from functools import lru_cache

class Solution:

    @lru_cache(maxsize=None)
    def recursiveWithMemo(self, index, s) -> int:
        if index == len(s):
            return 1

        if s[index] == "0":
            return 0

        if index == len(s) - 1:
            return 1

        answer = self.recursiveWithMemo(index + 1, s)
        if int(s[index: index + 2]) <= 26:
            answer += self.recursiveWithMemo(index + 2, s)

        return answer

    def numDecodings(self, s: str) -> int:
        return self.recursiveWithMemo(0, s)

func recursiveWithMemo(index int, str string, memo
map[int]int) int {
    if val, ok := memo[index]; ok {
        return val
    }
    if index == len(str) {
        return 1
    }
    if str[index] == '0' {
        return 0
    }
    if index == len(str)-1 {
        return 1
    }
    ans := recursiveWithMemo(index+1, str, memo)
    substrNum, _ := strconv.Atoi(str[index : index+2])
    if substrNum <= 26 {
        ans += recursiveWithMemo(index+2, str, memo)
    }
    memo[index] = ans
    return ans
}

func numDecodings(s string) int {
    memo := make(map[int]int)
    return recursiveWithMemo(0, s, memo)
}

Explanation

Algorithm

1️⃣

Входим в рекурсию с данной строкой, начиная с индекса 0.

2️⃣

Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3️⃣

Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.

😎