Skip to content

Instantly share code, notes, and snippets.

@flangofas
Last active January 18, 2019 12:56
Show Gist options
  • Save flangofas/4c6aa216fba12c66b2273999363d9a11 to your computer and use it in GitHub Desktop.
Save flangofas/4c6aa216fba12c66b2273999363d9a11 to your computer and use it in GitHub Desktop.
Interview programming question Get the
<?php
/*
* Intreview question
*
* Build a function that returns common and longest sub-sequence of
* the two strings.
*
* For example,
* AAAA,AA outputs: AA
* AGGTAB, GXTXAYB outputs: GTAB
* ABAZDC, BACBAD outputs: ABAD
**/
function commonLongestSubSequence(string $s1, string $s2) :string
{
$longest = 0;
$subSequence = "";
$s1AsArray = str_split($s1);
foreach ($s1AsArray as $index => $s1Char) {
$tempS1 = substr($s1, $index);
$ss = buildSubSequence($tempS1, $s2);
if (empty($ss)) {
continue;
}
$length = strlen($ss);
if ($length > $longest) {
$longest = $length;
$subSequence = $ss;
}
}
return $subSequence;
}
function buildSubSequence(string $s1, string $s2) :string
{
$subSequence = "";
foreach (str_split($s1) as $s1Char) {
$pos = strpos($s2, $s1Char);
if ($pos === false) {
continue;
}
//Create a sub str and exclude
$s2 = substr($s2, $pos + 1);
$subSequence .= $s1Char;
}
return $subSequence;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment