Проверить равенство для каждого подмножества строку s в соответствии с целевым T и возвращает число


Я написал следующий код, чтобы решить эту проблему leetcode:

var numDistinct = function(s, t) {
    if (!s.length) return +(!t.length);
    let res = 0;
    for (let seq of subseq(s)) res += +(t===seq);
    return res; 
};
var subseq = function(a) {
    if (a.length==1) return [a[0], ''];
    let subsets = subseq(a.substr(0, a.length-1));
    let n = subsets.length;
    for (let i=0; i < n; i++) {
       subsets.push(subsets[i]+a[a.length-1]);
    }
    return subsets;
};

Очевидно, этот код не является эффективным, так как он генерирует каждый из \$2^п\$ подмножеств строк s и проверяет каждого на равенство против t.

Я бы очень признателен, если кто-то может объяснить, как улучшить это решение с использованием мемоизации. Я знаю, что есть динамическое программирование решение. Я более заинтересован в обучении, как продлить это легко понять решения в что-то более эффективное с помощью памятки таблицы. Любой и вся помощь будет любезно оценили.



Комментарии
1 ответ

Я просто хочу отметить, что код ИМХО имеет слишком много "оптимизация длины". Просто берем первую строчку:

if (!s.length) return +(!t.length);

Я на JS разработчиков уже более 20 лет и я не могу сказать с верхней части моей голове, что + не логическое. Было бы гораздо более читаемым как:

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

Также комментарий, почему они имеют правильные значения, вернуться будет очень полезно.

0
ответ дан 13 февраля 2018 в 09:02 Источник Поделиться