jasonj79
BAN USERPHP version:
function numberToPossibleStrings($num, $numToCharMap) {
// convert number to string, extract digits
$numLen = strlen("$num");
// no possible matches, return empty
if ($numLen == 0 || $num == 0) {
return array();
}
// init an array with element 0 pre filled
$combinations = array('');
// init our recursive algo
processDigit($num, $numLen, 0, $combinations, 0, $numToCharMap);
return $combinations;
}
function processDigit($num, $numLen, $numAt, &$combinations, $combinationsAt, $numToCharMap) {
// verify we are within index
if ($numAt >= $numLen) {
return;
}
$singleNum = substr("$num", $numAt, 1);
// if current digit is 0, move ahead one space
if ($singleNum == 0) {
return processDigit($num, $numLen, $numAt + 1, $combinations, $combinationsAt, $numToCharMap);
}
// handle double case first, as it creates a new array item
if ($numAt + 1 < $numLen) {
$doubleNum = (int)substr("$num", $numAt, 2);
if ($doubleNum < 27) {
// doubles create a new entry, and increment the combinations offset
$combinations[] = $combinations[$combinationsAt] . $numToCharMap[$doubleNum];
processDigit($num, $numLen, $numAt + 2, $combinations, count($combinations) - 1, $numToCharMap);
}
}
// handle single case
$combinations[$combinationsAt] = $combinations[$combinationsAt] . $numToCharMap[$singleNum];
processDigit($num, $numLen, $numAt + 1, $combinations, $combinationsAt, $numToCharMap);
}
// setup number to char map
$numToCharMap = array();
for ($j = 1; $j < 27; $j++) {
$numToCharMap[$j] = chr($j + 96);
}
print_r(numberToPossibleStrings(1123, $numToCharMap));
print_r(numberToPossibleStrings(1010, $numToCharMap));
print_r(numberToPossibleStrings(1000, $numToCharMap));
print_r(numberToPossibleStrings(237811487, $numToCharMap));
PHP version
Part 1: print all paths of a binary tree
// class for Binary Tree Node
class BinaryNode {
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = $value;
$this->left = null;
$this->right = null;
}
public function isLeaf() {
return ($this->left === null && $this->right === null);
}
}
// Class for Binary Tree
class BinaryTree {
private $_root;
public function __construct() {
$this->_root = null;
}
public function isEmpty() {
return $this->_root === null;
}
public function insert($value) {
$node = new BinaryNode($value);
if ($this->isEmpty()) {
$this->_root = $node;
} else {
$this->_insertNode($node, $this->_root);
}
}
private function _insertNode(BinaryNode $node, &$subTree) {
if ($subTree === null) {
$subTree = $node;
}
// right insert
elseif ($node->value > $subTree->value) {
$this->_insertNode($node, $subTree->right);
}
// left insert
elseif ($node->value < $subTree->value) {
$this->_insertNode($node, $subTree->left);
}
}
public function getRoot() {
return $this->_root;
}
}
function printAllTreePaths(BinaryTree $tree) {
$root = $tree->getRoot();
$treePath = '';
recurseNode($root, $treePath);
}
function recurseNode(BinaryNode $node, $treePath) {
$treePath .= $node->value;
// if we've hit a leaf, print the current path
if ($node->isLeaf()) {
echo $treePath . "\n";
return;
}
// check and recurse left node
if ($node->left !== null) {
recurseNode($node->left, $treePath . '<L>');
}
// check and recurse right node
if ($node->right !== null) {
recurseNode($node->right, $treePath . '<R>');
}
}
// create and fill the tree
$myTree = new BinaryTree();
for ($i = 0; $i < 100; $i++) {
$myTree->insert(mt_rand(1,10000));
}
// print the tree
printAllTreePaths($myTree);
Implemented in PHP because why not :)
function phoneToText($phoneNumber) {
// storage for our found words
$foundWords = array();
// cast number / digits to a string, then to an array
$phoneDigits = str_split((string)$phoneNumber);
foreach ($phoneDigits as $digit) {
processDigit($digit, $foundWords);
}
return $foundWords;
}
function processDigit($digit, &$foundWords) {
// hash of phone digits to characters
static $numToCharHash = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
// return if digit has no characters
if (!isset($numToCharHash[$digit])) {
return;
}
// if we have no existing entries, add current characters and return
if (count($foundWords) == 0) {
$foundWords = $numToCharHash[$digit];
return;
}
// append the first char to each word
for ($j = 0, $wordsLen = count($foundWords); $j < $wordsLen; $j++) {
$t = $foundWords[$j];
// first, append the existing entry with the first char
$foundWords[$j] .= $numToCharHash[$digit][0];
// add new entries for the other chars
for ($i = 1, $charCount = count($numToCharHash[$digit]); $i < $charCount; $i++) {
$foundWords[] = $t . $numToCharHash[$digit][$i];
}
}
return;
}
PHP version
function hasAnagrams($stringsArray) {
// keep a hash of the ordered words
$stringsOrderedHash = array();
foreach ($stringsArray as $word) {
// skip blanks
if (!$word) {
continue;
}
// lowercase the word, as anagrams should match regardless of case???
$word = strtolower($word);
// convert word to array
$wordArray = str_split($word);
// sort resultant letters
sort($wordArray);
$wordSorted = implode($wordArray);
// key exists, has anagrams
if (isset($stringsOrderedHash[$wordSorted])) {
return true;
}
// add to hash as key to allow index lookup
$stringsOrderedHash[$wordSorted] = 1;
}
// ran out of words to check, so no anagrams
return false;
}
Iterative approach in PHP, runs O(n)
function OneEditApart($s1, $s2) {
// only calc these once
$s1Len = strlen($s1);
$s2Len = strlen($s2);
// 0 edits apart, return false
if ($s1 == $s2) {
return false;
}
// we want the shorter as the first param
if ($s1Len > $s2Len) {
return OneEditApart($s2, $s1);
}
// if lengths differ by more than 1, return false
if ($s2Len - $s1Len > 1) {
return false;
}
// keep current indexes of both words
$s1i = $s2i = $edits = 0;
while ($s1i < $s1Len && $s2i < $s2Len) {
// break processing and return if we have achieved more than one edit
if ($edits > 1) {
return false;
}
// if letters match, next
if ($s1[$s1i] == $s2[$s2i]) {
$s1i++;
$s2i++;
continue;
}
// insert case
if ($s1[$s1i] == $s2[$s2i + 1]) {
$edits++;
$s1i++;
$s2i = $s2i + 2;
continue;
}
// remove case
if ($s1[$s1i + 1] == $s2[$s2i]) {
$edits++;
$s1i = $s1i + 2;
$s2i++;
continue;
}
// replace case
$edits++;
$s1i++;
$s2i++;
}
// get index difference, as it will impact our remaining length calc
$iDiff = $s2i - $s1i;
// add any differences in word lengths minus previous diff to inserts
$edits = $edits + ($s2Len - $s1Len - $iDiff);
if ($edits == 1) {
return true;
}
// more or less than 1
return false;
}
In python
- jasonj79 June 07, 2014