1416. Restore The Array

leetcode hard

#array#csharp#dynamic-programming#graph#hard#leetcode#recursion#string#tree

Task

Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.

Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: s = "1000", k = 10000

Output: 1

Explanation: The only possible array is [1000]

C# solution

matched/original

public class Solution {
    private int mod = 1_000_000_007;
    private int Dfs(int[] dp, int start, string s, int k) {
        if (dp[start] != 0) return dp[start];
        if (start == s.Length) return 1;
        if (s[start] == '0') return 0;
        long count = 0;
        for (int end = start; end < s.Length; ++end) {
            string currNumber = s.Substring(start, end - start + 1);
            if (long.Parse(currNumber) > k) break;
            count = (count + Dfs(dp, end + 1, s, k)) % mod;
        }
        dp[start] = (int)count;
        return (int)count;
    }
    public int NumberOfArrays(string s, int k) {
        int[] dp = new int[s.Length + 1];
        return Dfs(dp, 0, s, k);
    }
}

C++ solution

auto-draft, review before submit

#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 int mod = 1_000_000_007;
    private int Dfs(vector<int>& dp, int start, string s, int k) {
        if (dp[start] != 0) return dp[start];
        if (start == s.size()) return 1;
        if (s[start] == '0') return 0;
        long count = 0;
        for (int end = start; end < s.size(); ++end) {
            string currNumber = s.Substring(start, end - start + 1);
            if (long.Parse(currNumber) > k) break;
            count = (count + Dfs(dp, end + 1, s, k)) % mod;
        }
        dp[start] = (int)count;
        return (int)count;
    }
    public int NumberOfArrays(string s, int k) {
        vector<int>& dp = new int[s.size() + 1];
        return Dfs(dp, 0, s, k);
    }
}

Java solution

matched/original

class Solution {
    int mod = 1_000_000_007;

    private int dfs(int[] dp, int start, String s, int k) {
        if (dp[start] != 0)
            return dp[start];

        if (start == s.length())
            return 1;

        if (s.charAt(start) == '0')
            return 0;

        int count = 0;
        for (int end = start; end < s.length(); ++end) {
            String currNumber = s.substring(start, end + 1);
            if (Long.parseLong(currNumber) > k)
                break;
            count = (count + dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = count;
        return count;
    }
    
    public int numberOfArrays(String s, int k) {
        int m = s.length();
        int[] dp = new int[m + 1];
        return dfs(dp, 0, s, k);
    }
}

JavaScript solution

matched/original

var Solution = function() {
    this.mod = 1_000_000_007;
};

Solution.prototype.dfs = function(dp, start, s, k) {
    if (dp[start] !== 0) return dp[start];
    if (start === s.length) return 1;
    if (s[start] === '0') return 0;

    let count = 0;
    for (let end = start; end < s.length; end++) {
        let currNumber = parseInt(s.slice(start, end + 1));
        if (currNumber > k) break;
        count = (count + this.dfs(dp, end + 1, s, k)) % this.mod;
    }

    dp[start] = count;
    return count;
};

Solution.prototype.numberOfArrays = function(s, k) {
    let dp = Array(s.length + 1).fill(0);
    return this.dfs(dp, 0, s, k);
};

Go solution

matched/original

func dfs(dp []int, start int, s string, k int) int {
    if dp[start] != 0 {
        return dp[start]
    }
    if start == len(s) {
        return 1
    }
    if s[start] == '0' {
        return 0
    }

    mod := 1_000_000_007
    count := 0
    for end := start; end < len(s); end++ {
        currNumber, _ := strconv.Atoi(s[start : end+1])
        if currNumber > k {
            break
        }
        count = (count + dfs(dp, end+1, s, k)) % mod
    }

    dp[start] = count
    return count
}

func numberOfArrays(s string, k int) int {
    dp := make([]int, len(s)+1)
    return dfs(dp, 0, s, k)
}

Explanation

Algorithm

Создать массив dp размера m + 1, чтобы хранить значения dfs(x).

Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:

Если s[start] == 0, вернуть 0.

Если start = m, вернуть 1.

Инициализировать count = 0, чтобы считать количество возможных массивов.

Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).

Обновить dp[start] значением dfs(start).

Вернуть dfs(0).

😎