最長共通部分列問題

アルゴリズムの勉強をしたので、晒します。
問題はコチラ。

2つの文字列S1,S2,...,SnとT1,T2,...,Tmが与えられます。
これら2つの共通部分列の長さの最大値を求めなさい。
ただし、文字列S1,S2,...,Snの部分文字列とは、Si1,Si2,...,Sim(i1<i2<...<im)と表すことができる文字列のことをいいます。

制約：
・1 <= n, m <= 1000

で、私の回答がコチラ。

<?php
class LongSamePartSet
{
    public function calc($firstWords, $secondWords)
    {
        $maxLengths = [];
        for ($i = mb_strlen($firstWords) - 1; $i >= 0; $i--) {
            $selfLengths = [];
            for ($j = mb_strlen($secondWords) - 1; $j >= 0; $j--) {
                if ($firstWords[$i] === $secondWords[$j]) {
                    $length = 0;
                    foreach ($maxLengths as $index => $maxLength) {
                        if ($j < $index && $length < $maxLength) {
                            $length = $maxLength;
                        }
                    }
                    $selfLengths[$j] = $length + 1;
                }
            }
            $maxLengths = $selfLengths + $maxLengths;
        }
        return count($maxLengths) === 0 ? 0 : max($maxLengths);
    }
}

forが3回呼ばれてるので、何か遅そう。。。
会社の先輩のコードは、2回しか呼ばれてませんでした。
SとTを使って、共通部分列をマトリクスで表し、小さい方から順番に求めると・・・うーん、言葉では説明しづらい。
そのうちリファクタしてみようと思います。

【追記】リファクタしました！

class LongestCommonSubsequence
{
    public static function calc($firstWords, $secondWords)
    {
        $note = [];
        for ($i = 0; $i <= mb_strlen($firstWords); $i++) {
            $note[$i] = [];
            if ($i === 0) {
                for ($j = 1; $j <= mb_strlen($secondWords); $j++) {
                    $note[$i][$j] = 0;
                }
                continue;
            }
            $note[$i][0] = 0;
        }

        for ($i = 0; $i < mb_strlen($firstWords); $i++) {
            for ($j = 0; $j < mb_strlen($secondWords); $j++) {
                if ($firstWords[$i] === $secondWords[$j]) {
                    $note[$i + 1][$j + 1] = $note[$i][$j] + 1;
                } else {
                    $note[$i + 1][$j + 1] = max($note[$i][$j + 1], $note[$i + 1][$j]);
                }
            }
            unset($note[$i]);
        }
        return $note[mb_strlen($firstWords)][mb_strlen($secondWords)];
    }
}

【追記】リファクタしました！その２

実は、前回のリファクタは、会社の先輩のコードを真似たものでした。
が、悔しいので、自分自身のコードをリファクタしてみました。
（バグってたので直しました・・←３度目

class LongestCommonSubsequence
{
    public static function calc($firstWords, $secondWords)
    {
        $maxLengths = [];
        for ($i = mb_strlen($firstWords) - 1; $i >= 0; $i--) {
            $checkLengths = [];
            $checkMaxLength = 0;
            for ($j = mb_strlen($secondWords) - 1; $j >= 0; $j--) {
                if (array_key_exists($j + 1, $maxLengths)) {
                    $checkMaxLength = max($checkMaxLength, $maxLengths[$j + 1]);
                }
                $checkLengths[$j] = $checkMaxLength;
            }
            $selfLengths = [];
            for ($j = mb_strlen($secondWords) - 1; $j >= 0; $j--) {
                if ($firstWords[$i] === $secondWords[$j]) {
                    $selfLengths[$j] = $checkLengths[$j] + 1;
                }
            }
            $maxLengths = $selfLengths + $maxLengths;
        }
        return count($maxLengths) === 0 ? 0 : max($maxLengths);
    }
}