JavaScriptで2つの文字列を一致させるための削除文字ASCII値合計の最小化

問題

本記事では、英小文字のみで構成された2つの文字列 str1 と str2 をそれぞれ第1・第2引数として受け取るJavaScript関数の作成方法を解説します。

この関数の目的は、2つの文字列を完全に等しくするために削除しなければならない文字のASCII値の合計を求め、そのうち最小となる値を返すことです。

例として、関数への入力が以下の場合を考えてみましょう。

入力

const str1 = 'sea';
const str2 = 'eat';

出力

const output = 231;

出力の解説

まず、「sea」から「s」を削除すると、「s」のASCII値である 115 が合計に加算されます。

次に、「eat」から「t」を削除すると、116 が合計に加算されます。

この時点で両方の文字列は「ea」となり等しくなります。したがって、115 + 116 = 231 が、2つの文字列を一致させるために必要な削除文字のASCII値合計の最小値となります。

アプローチのポイント

この問題は動的計画法(DP)を用いることで効率的に解けます。各状態を「str1のある位置以降とstr2のある位置以降を一致させるのに必要な削除コストの最小値」と捉えます。対応する文字同士が一致する場合はコストなしで次の状態へ進み、一致しない場合はどちらか一方の文字を削除した場合のコストの小さい方を選択します。

境界条件として、片方の文字列の末尾に達した場合には、もう片方の残りの文字すべてのASCII値を合計した値が必要になります。この実装では二次元配列の代わりに1行分の配列をローリングさせて使うことで、メモリ使用量を抑えています。

コード例

以下が実際のコードです −

const str1 = 'sea';
const str2 = 'eat';
const minimumSum = (str1 = '', str2 = '') => {
    const chartCode = (s = '') => {
        let code = 0
        for (const c of s) {
            code += c.charCodeAt(0)
        }
        return code
    }
    let prev = new Array(str2.length + 1).fill(0)
    for (let ind1 = str1.length; ind1 >= 0; ind1--) {
        const current = new Array(str2.length + 1).fill(0)
        for (let ind2 = str2.length; ind2 >= 0; ind2--) {
            if (ind1 === str1.length) {
                current[ind2] = chartCode(str2.slice(ind2))
            } else if (ind2 === str2.length) {
                current[ind2] = chartCode(str1.slice(ind1))
            } else if (str1[ind1] === str2[ind2]) {
                current[ind2] = prev[ind2 + 1]
            } else {
                current[ind2] = Math.min(
                    prev[ind2] + (str1[ind1]).charCodeAt(0),
                    current[ind2 + 1] + (str2[ind2]).charCodeAt(0),
                )
            }
        }
        prev = current
    }
    return prev[0]
}
console.log(minimumSum(str1, str2));

出力

231