javascript - 尝试为不起作用的最大公共子字符串编写一个记忆解决方案

Question

我已经为 LCS 编写了这个记忆化的解决方案，但它似乎不起作用。我究竟做错了什么？

const lcsMemo = (s1, s2) => {
    let i = 0, j = 0
    const memo = Array.from(new Array(s1.length), () => Array(s2.length).fill(''))
    console.log(memo);


    const helper = (s1, s2, i, j, memo) => {
        if (i === s1.length || j === s2.length) return 0

        if (memo[i][j]) return memo[i][j]

        if (s1[i] === s2[j]) {
            return 1 + helper(s1, s2, i + 1, j + 1, memo)
        }

        else {
            return memo[i][j] = Math.max(helper(s1, s2, i + 1, j, memo), helper(s1, s2, i, j + 1, memo))
        }
    }
    return helper(s1, s2, i, j, memo)
}

我将它包含在此函数中以解决称为 common child 的 HackerRank 问题。我有 9/15 次测试通过，但是我无法查看的失败测试因消息运行时错误而失败。HackerRank 网站的运行时错误说明了该错误：

Your code terminated unexpectedly. Did you overrun your array? Is your code trying to divide by zero?

const commonChild = (s1, s2) => {
    const arr1 = [],
        arr2 = []


    for (let [i, letter] of [...s1].entries()) {
        let index = s2.indexOf(letter)
        if (index > -1) {
            arr1.push(letter)
        }
    }
    for (let [i, letter] of [...s2].entries()) {
        let index = s1.indexOf(letter)
        if (index > -1) {
            arr2.push(letter)
        }
    }

    console.log(arr1.join(''));
    console.log(arr2.join(''));

    const lcsMemo = (s1, s2) => {
        let i = 0, j = 0
        const memo = Array.from(new Array(s1.length), () => Array(s2.length).fill(''))

        const helper = (s1, s2, i, j, memo) => {
            if (i === s1.length || j === s2.length) return 0

            if (memo[i][j]) return memo[i][j]

            if (s1[i] === s2[j]) {
                return 1 + helper(s1, s2, i + 1, j + 1, memo)
            }

            else {
                return memo[i][j] = Math.max(helper(s1, s2, i + 1, j, memo), helper(s1, s2, i, j + 1, memo))
            }
        }
        return helper(s1, s2, i, j, memo)
    }

    return lcsMemo(arr1.join(''), arr2.join(''))
}

一些测试用例是：

console.log(commonChild('SHINCHAN', 'NOHARAAA')) //3 NHA
console.log(commonChild('AA', 'BB')) //0
console.log(commonChild('HARRY', 'SALLY')) //2 AY
console.log(commonChild('ABCDEF', 'FBDAMN')) //2 BD

标签： javascriptstringalgorithmdynamic-programmingmemoization