giladsoffer
BAN USERfor each string- sort it and put in a map where the key is the sorted string.
O( n*klogk )
function func($arr) {
$res = array();
foreach($arr as $string) {
$chars = str_split($string);
sort($chars);
$chars = implode($chars);
$res[$chars] []= $string;
}
return $res;
}
Keep an out-side array and fill it by in-order traversal - if this array is ascending then we have a BST
function func($root) {
$arr = array(-10000);
inOrderCheck($root,$arr);
return $arr !== false;
}
function inOrderCheck($node,&$arr) {
if ($node) {
inOrderCheck($node['left'],$arr);
if ($arr !== false && end($arr) < $node['val']) {
$arr []= $node['val'];
} else {
$arr = false;
}
inOrderCheck($node['right'],$arr);
}
}
function func($pattern,$string) {
if (strpos($pattern,"**") !== false || strpos($pattern,"*") === 0)
return false;
$pi = 0;
$si = 0;
do {
$p_chr = $pattern[$pi];
$s_chr = $string[$si];
if ($p_chr == $s_chr || $p_chr == '.') {
$pi++;
$si++;
} elseif ($p_chr == '*') {
$masterChar = $string[$si-1];
while ($string[$si] == $masterChar) $si++;
$pi++;
} elseif ($pattern[$pi+1] == '*') {
$pi+=2;
} else {
return false;
}
}while($p_chr != null || $s_char != null);
return true;
}
var_dump(func("aaa","aaa") == true);
var_dump(func("aaak","aaa") == false);
var_dump(func("aaa","aaak") == false);
var_dump(func("a.a","ana") == true);
var_dump(func(".aa.","jaan") == true);
var_dump(func("aaa","bbb") == false);
var_dump(func(".aa","bbb") == false);
var_dump(func("ab*g","ag") == true);
var_dump(func("ab*g","abg") == true);
var_dump(func("ab*g","abbg") == true);
var_dump(func("ab*","abbb") == true);
var_dump(func("b*","") == true);
var_dump(func(".*.","jjjjjm") == true);
var_dump(func("*aaa","a") == false);
var_dump(func("aa***a","a") == false);
var_dump(func(".","j") == true);
$A = array(
array(
array(0,1),array(1,2),array(3,3)
),
array(
array(1,1),array(3,3),array(3,2)
),
array(
array(3,0),array(1,3),null
),
);
$hasBeen = array();
$rootPosition = array(0,0);
$total = 0;
var_dump(func($A,$rootPosition,$total,$hasBeen));
function func($A,$position,$total,$hasBeen) {
$item = $A[$position[0]][$position[1]];
if ($item == null) {
return $total == count($A)*count($A);
}
$hasBeen []= $position;
$nextPosition = array($item[0],$item[1]);
if (!in_array($nextPosition,$hasBeen)) {
return func($A,$nextPosition,$total+1,$hasBeen);
}
return false;
}
- giladsoffer February 15, 2014