問題
文字列 a と b を
- 拾う
文字は 隣どうしでなくて 構いません。 ただし、 元の 文字列での 順番は 変えられません - 共通の
部分列が 1 文字も 無ければ 0 を返します aとbの長さは、 どちらも 0 以上 1000 以下です。 空の 文字列も来ます - 文字は
英小文字だけです
入力と出力の例
例 1
s、
入力
a = "stream"
b = "master"出力
3例 2
b のa の
入力
a = "programming"
b = "gaming"出力
6例 3
同じ
入力
a = "sky"
b = "dawn"出力
0面接での聞かれ方
面接では、
- 「2 つの
文字列の、 最長の 共通部 分列の 長さを 返してください」 - 最初に
「部分文字列 (続いた 文字) ではなく 部分列ですね？」と 確かめられるかを 見られます - 書き終えると
「表を 2 行に 減らせますか？」 「長さではなく、 部分列 その ものを 返せますか？」と続きます
「部分列」は
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
まずはa からb の
段 2
前からa のb のt[i][j] とt[i-1][j-1] に 1 をa のt[i-1][j] と、b のt[i][j-1] の
段 3
表のprev と cur で
解答
Python
Python
def common_length(a, b):
n = len(b)
prev = [0] * (n + 1)
for x in a:
cur = [0] * (n + 1)
for j in range(n):
up = prev[j + 1]
left = cur[j]
v = max(up, left)
if x == b[j]:
v = prev[j] + 1
cur[j + 1] = v
prev = cur
return prev[n]JavaScript
JavaScript
function commonLength(a, b) {
const n = b.length;
let prev = Array(n + 1)
.fill(0);
for (const x of a) {
const cur = Array(n + 1)
.fill(0);
let j = 0;
for (const y of b) {
const up = prev[j + 1];
const left = cur[j];
let v = prev[j] + 1;
if (x !== y) {
v = Math.max(up, left);
}
cur[j + 1] = v;
j++;
}
prev = cur;
}
return prev[n];
}Go
Go
func commonLength(
a, b string,
) int {
n := len(b)
prev := make([]int, n+1)
for i := 0; i < len(a); i++ {
cur := make([]int, n+1)
for j := 0; j < n; j++ {
up := prev[j+1]
left := cur[j]
v := max(up, left)
if a[i] == b[j] {
v = prev[j] + 1
}
cur[j+1] = v
}
prev = cur
}
return prev[n]
}prev[j] がprev[j + 1] がcur[j] が
計算量
- 時間は O(m × n) です (m は
a、n は bの長さ)。 表の 欄を 1 つずつ 埋めます。 1000 文字どうしなら 100 万欄です - 使う
記憶は O(n) です。 生きている 並びは prevとcurの 2 行分だけです - 2 次元の
表を そのまま 持つ 書き方は、 時間は 同じで 記憶が O(m × n) です。 部分列 その ものを 返したい ときは、 表を 全部持って右下から 戻る 道を たどるので、 こちらの 書き方を使います
よく
- 部分文字列と
取り違える。 続いた 文字だけを 数えると、 例 2 は 「ming」の 4 に なってしまいます。 部分列は 飛び飛びで よいので 6 です - 同じ
文字の ときに 上や左に 1 を足す。 1 を 足して よいのは 左上だけです。 左に 足すと、 aの同じ 文字を bの 2 つの文字に 合わせて 数える ことになります。 たとえば a = "a"、b = "aa"で 2 を返したら、 この 間違いです - 欲張りで
前から 合わせる。 aの文字を 前から 順に、 bの中で 次に 出てくる 所へ 合わせていく と外れます。 a = "xab"、b = "abx"では、先頭の x を bの最後の x に 合わせた 時点で、 残りの a と b を 合わせる 場所が なくなり 1 に なります。 答えは a と b の 2 です - 表の
大きさを 1 つ少なく取る。 空の 前置きを 表すために、 縦も 横も 長さより 1 つ 多く 取ります。 番号の ずれで、 最後の 文字を 見落としやすくなります
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「部
分列は 飛び飛びで よいので、 全部試すと 2 の m 乗通りです。 前から i 文字と j 文字での 答えを 表にし、 最後の 文字が 同じなら左上に 1 を 足し、 違えば 上と 左の 大きい ほうを 取ります。 使うのは 1 つ前の 行だけなので、 2 行分の 並びで 記憶は O(n)、 時間は O(m × n) です。」
書き終えたら、
「例 1 の
streamとmasterでたどります。 masterの s にstreamの s が合って 1、 その 後ろの t に t が 合って 2 です。 streamの r はmasterの最後の r と 合い、 それまでの 2 に 1 を 足して 3 に なります。 e や a や m は、 順番を 守ると 4 文字目として 足せないので、 答えは 3 です。」