javascript - 使用 JavaScript 优化递归字符串操作函数

Question

问题

我今天在算法课上遇到了这个问题:

Given function maxSubstring(s, t), where s is a string and t is a substring of s, find the maximum number of iterations you can delete either the first or last occurrence of substring t .

概念

这是在 s = banababbaa 和 t = ba 上调用的函数 maxSubstring 的可视化。

          b  a  n  a  b  b  a  a
1st move: n  a  b  a  b  b  a            or   b  a  n  a  b  a  b  a
2nd move: n a b b a a  or  n a b a b a        n a b a b a  or  b a n a b a
3rd move:    n a b a   or   n a b a             n a b a    or    n a b a
4th move:             n  a                                n  a

因此，此操作需要四步。

尝试

这是我对这个问题的解决方案。它可以工作，但是当我使用较大的字符串作为参数时速度很慢。

尝试 #1

function maxSubstring(s, t) {
    if (s.includes(t)) {
        var idxSubstr = s.replace(t, '');
        var lastIdxSubstr = s.substr(0, s.lastIndexOf(t)) + s.substr(s.lastIndexOf(t) + t.length, s.length);
        return 1 + Math.max(maxSubstring(idxSubstr, t), maxSubstring(lastIdxSubstr, t)));
    }
    return 0;
}

尝试#2

function maxSubstring(s, t) {
    if (s.includes(t)) {
        var idx = s.indexOf(t), lastIdx = s.lastIndexOf(t);
        var idxSubstr = s.substr(0, idx) + s.substr(idx + t.length, s.length);
        var lastIdxSubstr = s.substr(0, lastIdx) + s.substr(lastIdx + t.length, s.length);
        if (idx != lastIdx) {
            return 1 + Math.max(maxSubstring(idxSubstr, t), maxSubstring(lastIdxSubstr, t));
        } else {
            return 1 + maxSubstring(idxSubstr, t);
        }
    }
    return 0;
}

更新原因:通过将 indexOf 和 lastIndexOf 的值存储在变量中，效率发生了微小变化。

尝试#3

function maxSubstring(s, t) {
    var idx = s.indexOf(t);
    if (idx >= 0) {
        var lastIdx = s.lastIndexOf(t);
        var idxSubstr = s.substr(0, idx) + s.substr(idx + t.length);
        if (idx != lastIdx) {
            var lastIdxSubstr = s.substr(0, lastIdx) + s.substr(lastIdx + t.length);
            return 1 + Math.max(maxSubstring(idxSubstr, t), maxSubstring(lastIdxSubstr, t));
        } else {
            return 1 + maxSubstring(idxSubstr, t);
        }
    }
    return 0;
}

更新原因:减少了在检查第一个索引之前重新定义某些值并阻止 lastIndexOf 计算的实例。

回答要求

我可以使用任何算法或方法来优化这段代码吗？ Math.max 是罪魁祸首，所以如果有人知道如何完全避免使用此方法，我将不胜感激。

换句话说，maxSubstring 只应在其内部调用一次，但 Math.max 要求调用两次(一次用于子字符串的第一个索引另一次是该子字符串的最后一个索引)。

最后，您介意告诉我大 O 表示法对我的解决方案是什么以及大 O 表示法对您的解决方案是什么吗？这不是最初挑战的一部分，但我自己很好奇。提前致谢。

Answer 1

您提出的朴素递归算法的主要问题是它在相同的输入 s 上被调用的频率非常高 - 甚至呈指数增长，而这正是导致 明显的原因 较大字符串的减速。

你可以做的是使用 memoisation - 记住查找表中特定输入的结果。

您可以做的另一个优化是检查删除第一个和最后一个是否会导致不同的结果。在大多数情况下，删除它们的顺序绝对无关紧要，可能删除的次数始终相同。但是，当匹配的子字符串可以与自身重叠时，情况就不是这样了。例如，尝试 maxSubstring('ababa', 'aba')。

function maxSubstring(s, t, prevResults = new Map()) {
    function result(x) { prevResults.set(s, x); return x; }
    if (prevResults.has(s))
        return prevResults.get(s); // memoisation

    const first = s.indexOf(t);
    if (first == -1)
        return result(0);
    const withoutFirst = s.slice(0, first) + s.slice(first + t.length);

    const last = s.lastIndexOf(t);
    if (last == first) // only one match
        return result(1 + maxSubstring(withoutFirst, t, prevResults));

    if (t.lastIndexOf(t.charAt(t.length-1), t.length-1) == -1 // last character of t is found nowhere else in t
        || !t.includes(s.charAt(first+t.length))) // character after the match can never be part of a match
        // so this match is always removed in the optimal sequence and it doesn't matter whether as first or last
        return result(1 + maxSubstring(withoutFirst, t, prevResults));

    const withoutLast = s.slice(0, last) + s.slice(last + t.length);
    if (t.indexOf(t.charAt(0), 1) == -1 // first character of t is found nowhere else in t
        || !t.includes(s.charAt(last - 1))) // character before the match can never be part of a match
        // so this match is always removed and it doesn't matter when
        return result(1 + maxSubstring(withoutLast, t, prevResults));

    return result(1 + Math.max(maxSubstring(withoutFirst, t, prevResults),
                               maxSubstring(withoutLast, t, prevResults)));
}

时间复杂度分析

递归调用的次数应该大致是移除次数的二次方。根据我的第二个建议，在最好的情况下(取决于模式)它可能会下降到线性。

对于每个调用，考虑线性搜索(indexOf、slice 等)和 Map 查找，尽管它们的平均复杂度随着输入变小并且模式通常在输入的早期发现，将小于该值。无论如何，复杂度是多项式的，而不是指数的。