abobola
BAN USER<?php
$dictionary = ['cap', 'cup', 'cod', 'fog', 'cut', 'hut', 'hot', 'hit', 'cat', 'cot', 'cog', 'dog'];
$results = search($dictionary, 'cat', 'dog');
var_dump($results);
/**
* @param string[] $dictionary
* @param string $start
* @param string $end
*
* @return int|null
*/
function search(array $dictionary, $start, $end)
{
$graph = prepareGraph($dictionary);
$path[$start] = [$start];
$queue[] = $start;
while($queue) {
$currentWord = current($queue);
$currentPath = $path[$currentWord];
if ($end === $currentWord) {
return count($currentPath) - 1;
}
if (false === isset($graph[$currentWord])) {
return null;
}
foreach($graph[$currentWord] as $nextWord) {
if (array_key_exists($nextWord, $path)) {
continue;
}
$queue[] = $nextWord;
$path[$nextWord] = array_merge($currentPath, [$nextWord]);
}
next($queue);
}
}
/**
* @param string[] $dictionary
*
* @return array
*/
function prepareGraph(array $dictionary)
{
$dictionary = array_map('str_split', $dictionary);
$result = [];
foreach ($dictionary as $word1) {
foreach ($dictionary as $word2) {
if (1 === count(array_diff_assoc($word1, $word2))) {
$result[implode('', $word1)][] = implode('', $word2);
}
}
}
return $result;
}
<?php
$S = [
range(1, 4),
range(30, 40),
range(20, 91),
range(8, 10),
range(6, 7),
range(3, 9),
range(9, 12),
range(11, 14)
];
$R = range(3, 13);
print_r(findMinSubset($S, $R));
/**
* @param array $S
* @param array $R
*
* @return array
*/
function findMinSubset(array $S, array $R)
{
$result = [];
while ($S && $R) {
$bestIndex = 0;
$bestResult = 0;
foreach ($S as $i => $s) {
$intersection = array_intersect($s, $R);
$cardinality = count($intersection);
if (0 === $cardinality) {
unset($S[$i]);
continue;
}
if ($cardinality > $bestResult) {
$bestResult = $cardinality;
$bestIndex = $i;
}
}
if (empty($S)) {
break;
}
$result[] = $S[$bestIndex];
$R = array_diff($R, $S[$bestIndex]);
unset($S[$bestIndex]);
}
return $result;
}
1. I'm checking if n1 and n2 are on the same tree by comparing their roots.
2. Going from n1 to the root, I'm checking if current node is a parent for n2, if yes, this is our result.
<?php
$n = [
11 => new Node(1, 18),
12 => new Node(2, 15, 11),
13 => new Node(16, 17, 11),
14 => new Node(3, 8, 12),
15 => new Node(9, 14, 12),
16 => new Node(4, 5, 14),
17 => new Node(6, 7, 14),
18 => new Node(10, 11, 15),
19 => new Node(12, 13, 15),
21 => new Node(1, 18),
22 => new Node(2, 15, 21),
23 => new Node(16, 17, 21),
24 => new Node(3, 8, 22),
25 => new Node(9, 14, 22),
26 => new Node(4, 5, 24),
27 => new Node(6, 7, 24),
28 => new Node(10, 11, 25),
29 => new Node(12, 13, 25),
];
$result = (new Collection($n))
->findClosestCommonParent(16, 15);
var_dump($result);
class Collection
{
/** @var array */
protected $n;
/**
* @param array $n, an associative array of Nodes with theirs ID's as keys
*/
public function __construct(array $n)
{
$this->n = $n;
}
/**
* @param int id1
* @param int id2
*
* @return Node|null
*/
public function findClosestCommonParent($id1, $id2)
{
if (false === isset($this->n[$id1])) {
throw new InvalidArgumentException();
}
if (false === isset($this->n[$id2])) {
throw new InvalidArgumentException();
}
$node1 = $this->n[$id1];
$node2 = $this->n[$id2];
if (false === $this->isTheSameTree($node1, $node2)) {
return null;
}
$result = $node1;
while ($result instanceof Node && false === $result->isParentFor($node2)) {
$result = $this->findParent($result);
}
return $result;
}
/**
* @param Node $node1
* @param Node $node2
*
* @return bool
*/
protected function isTheSameTree(Node $node1, Node $node2)
{
return $this->findRoot($node1) === $this->findRoot($node2);
}
/**
* @param Node $node
*
* @return Node|null
*/
protected function findParent(Node $node)
{
return isset($this->n[$node->parent]) ? $this->n[$node->parent] : null;
}
/**
* @param Node $node
*
* @return Node
*/
protected function findRoot(Node $node)
{
while (null !== $node->parent) {
$node = $this->findParent($node);
}
return $node;
}
}
class Node
{
/** @var int */
public $parent;
/** @var int */
public $left;
/** @var int */
public $right;
/**
* @param int $left
* @param int $right
* @param int|null $parent
*/
public function __construct($left, $right, $parent = null)
{
if ($left + 1 > $right) {
throw new InvalidArgumentException();
}
$this->left = $left;
$this->right = $right;
$this->parent = $parent;
}
/**
* @param Node $node
*
* @return bool
*/
public function isParentFor(Node $node)
{
return $this->left < $node->left && $this->right > $node->right;
}
}
<?php
$s = 'adobecodebanc';
$t = 'abc';
echo findMinSubstring($s, $t);
/**
* @param string $randomString
* @param string $uniqueString
*
* @return string
*/
function findMinSubstring($randomString, $uniqueString)
{
$minSubstring = $randomString;
while (strlen($randomString) > 0)
{
try {
$result = findSubstring($randomString, $uniqueString);
if (strlen($minSubstring) > strlen(current($result))) {
$minSubstring = current($result);
}
$randomString = substr($randomString, key($result) + 1);
}
catch (\Exception $e) {
break;
}
}
return $minSubstring;
}
/**
* @param string $randomString
* @param string $uniqueString
*
* @return array
*/
function findSubstring($randomString, $uniqueString)
{
$result = [];
foreach (str_split($uniqueString) as $letter) {
$result[$letter] = strpos($randomString, $letter);
if (false === $result[$letter]) {
throw new \Exception("No result");
}
}
asort($result);
$firstLetterPos = current($result);
$lastLetterPos = end($result);
$substring = substr($randomString, $firstLetterPos, $lastLetterPos - $firstLetterPos + 1);
return [$firstLetterPos => $substring];
}
RepThelmaDavis, business at A9
As a seasoned Housing Manager, I bring a wealth of experience in property management and a passion for creating comfortable ...
Repnetteyoder22, Applications Developer at 247quickbookshelp
Nette, transportation inspector inspects goods and equipment associated with transporting people or cargo to ensure safety. I typically work for ...
It will not work for nodes located on different levels.
- abobola January 06, 2016