freeCodeCamp/curriculum/challenges/japanese/10-coding-interview-prep/rosetta-code/longest-common-subsequence.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5e6dd1278e6ca105cde40ea9	最長共通部分列	5	385271	longest-common-subsequence

--description--

グループAおよびBの 最長共通部分列 (または LCS) とは、2つのグループ間で共通していて、各グループで同じ順序であるAおよびBの要素の最長グループです。 たとえば、数列 "1234" と "1224533324" の LCS は "1234" です。

1234

1224533324

文字列の例として、文字列 "thisisatest" と "testing123testing" の場合を考えてみましょう。 LCS は "tsitest" となります。

thisisatest

testing123testing.

今回のコードでは文字列のみを扱います。

この問題の詳細については、 Wikipedia を参照してください。

--instructions--

2 つの文字列の LCS を返す関数 (大文字と小文字を区別する) を記述してください。 複数の LCS を表示する必要はありません。

--hints--

lcs は関数とします。

assert(typeof lcs == 'function');

lcs("thisisatest", "testing123testing") は文字列を返す必要があります。

assert(typeof lcs('thisisatest', 'testing123testing') == 'string');

lcs("thisisatest", "testing123testing") は "tsitest" を返す必要があります。

assert.equal(lcs('thisisatest', 'testing123testing'), 'tsitest');

lcs("ABCDGH", "AEDFHR") は "ADH" を返す必要があります。

assert.equal(lcs('ABCDGH', 'AEDFHR'), 'ADH');

lcs("AGGTAB", "GXTXAYB") は "GTAB" を返す必要があります。

assert.equal(lcs('AGGTAB', 'GXTXAYB'), 'GTAB');

lcs("BDACDB", "BDCB") は "BDCB" を返す必要があります。

assert.equal(lcs('BDACDB', 'BDCB'), 'BDCB');

lcs("ABAZDC", "BACBAD") は "ABAD" を返す必要があります。

assert.equal(lcs('ABAZDC', 'BACBAD'), 'ABAD');

--seed--

--seed-contents--

function lcs(a, b) {

}

--solutions--

function lcs(a, b) {
  var aSub = a.substr(0, a.length - 1);
  var bSub = b.substr(0, b.length - 1);

  if (a.length === 0 || b.length === 0) {
    return '';
  } else if (a.charAt(a.length - 1) === b.charAt(b.length - 1)) {
    return lcs(aSub, bSub) + a.charAt(a.length - 1);
  } else {
    var x = lcs(a, bSub);
    var y = lcs(aSub, b);
    return (x.length > y.length) ? x : y;
  }
}