Input: letters = ["c","f","j"], target = "a"
Output: "c"

class WordFilter {
    private $prefixSuffixMap = [];
    
    function __construct($words) {
        foreach ($words as $index => $word) {
            $length = strlen($word);
            for ($prefixLength = 1; $prefixLength <= $length; $prefixLength++) {
                for ($suffixLength = 1; $suffixLength <= $length; $suffixLength++) {
                    $prefix = substr($word, 0, $prefixLength);
                    $suffix = substr($word, $length - $suffixLength);
                    $key = $prefix . '#' . $suffix;
                    $this->prefixSuffixMap[$key] = $index;
                }
            }
        }
    }
    
    function f($pref, $suff) {
        $key = $pref . '#' . $suff;
        return array_key_exists($key, $this->prefixSuffixMap) ? $this->prefixSuffixMap[$key] : -1;
    }
}

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

function longestStrChain($words) {
    usort($words, function($a, $b) {
        return strlen($a) - strlen($b);
    });
    
    $dp = [];
    $longestChain = 1;
    
    foreach ($words as $word) {
        $dp[$word] = 1;
        for ($i = 0; $i < strlen($word); $i++) {
            $predecessor = substr($word, 0, $i) . substr($word, $i + 1);
            if (isset($dp[$predecessor])) {
                $dp[$word] = max($dp[$word], $dp[$predecessor] + 1);
            }
        }
        $longestChain = max($longestChain, $dp[$word]);
    }
    
    return $longestChain;
}

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

class Solution {
    function tree2str($t) {
        $res = "";
        $this->dfs($t, $res);
        return $res;
    }

    function dfs($t, &$res) {
        if ($t == null)
            return;
        $res .= $t->val;
        if ($t->left == null && $t->right == null)
            return;
        $res .= '(';
        $this->dfs($t->left, $res);
        $res .= ')';
        if ($t->right != null) {
            $res .= '(';
            $this->dfs($t->right, $res);
            $res .= ')';
        }
    }
}

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

class Solution {
    function indexPairs($text, $words) {
        $wordsSet = array_flip($words);
        $ans = [];
        
        for ($i = 0; $i < strlen($text); $i++) {
            for ($j = $i; $j < strlen($text); $j++) {
                if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
                    $ans[] = [$i, $j];
                }
            }
        }
        return $ans;
    }
}

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

function isBoomerang($points) {
    list($x1, $y1) = $points[0];
    list($x2, $y2) = $points[1];
    list($x3, $y3) = $points[2];
    return ($x1 != $x2 || $y1 != $y2) && 
           ($x1 != $x3 || $y1 != $y3) && 
           ($x2 != $x3 || $y2 != $y3) && 
           ($x1 * ($y2 - $y3) + $x2 * ($y3 - $y1) + $x3 * ($y1 - $y2)) != 0;
}

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

class Solution {
    function pathSum($nums) {
        $tree = [];
        
        foreach ($nums as $num) {
            $depth = intdiv($num, 100);
            $pos = intdiv($num, 10) % 10;
            $val = $num % 10;
            $tree[$depth * 10 + $pos] = $val;
        }
        
        return $this->dfs($tree, 1, 1, 0);
    }
    
    private function dfs($tree, $depth, $pos, $currentSum) {
        $key = $depth * 10 + $pos;
        if (!isset($tree[$key])) {
            return 0;
        }
        $currentSum += $tree[$key];
        $leftChild = ($depth + 1) * 10 + 2 * $pos - 1;
        $rightChild = ($depth + 1) * 10 + 2 * $pos;
        if (!isset($tree[$leftChild]) && !isset($tree[$rightChild])) {
            return $currentSum;
        }
        return $this->dfs($tree, $depth + 1, 2 * $pos - 1, $currentSum) + $this->dfs($tree, $depth + 1, 2 * $pos, $currentSum);
    }
}

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

// PHP
class WordDistance {
    private $locations;

    function __construct($words) {
        $this->locations = [];
        foreach ($words as $i => $word) {
            if (!isset($this->locations[$word])) {
                $this->locations[$word] = [];
            }
            $this->locations[$word][] = $i;
        }
    }

    function shortest($word1, $word2) {
        $loc1 = $this->locations[$word1];
        $loc2 = $this->locations[$word2];
        $l1 = 0;
        $l2 = 0;
        $minDiff = PHP_INT_MAX;

        while ($l1 < count($loc1) && $l2 < count($loc2)) {
            $minDiff = min($minDiff, abs($loc1[$l1] - $loc2[$l2]));
            if ($loc1[$l1] < $loc2[$l2]) {
                $l1++;
            } else {
                $l2++;
            }
        }
        return $minDiff;

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $totalTilt = 0;
    
    function findTilt($root) {
        $this->sumAndTilt($root);
        return $this->totalTilt;
    }
    
    private function sumAndTilt($node) {
        if ($node === null) {
            return 0;
        }
        $leftSum = $this->sumAndTilt($node->left);
        $rightSum = $this->sumAndTilt($node->right);
        $nodeTilt = abs($leftSum - $rightSum);
        $this->totalTilt += $nodeTilt;
        return $node->val + $leftSum + $rightSum;
    }
}

Input: root = [4,2,6,1,3]
Output: 1

class Solution {
    private $inorderNodes = [];
    
    private function inorderTraversal($root) {
        if ($root === null) {
            return;
        }
        
        $this->inorderTraversal($root->left);
        $this->inorderNodes[] = $root->val;
        $this->inorderTraversal($root->right);
    }
    
    public function minDiffInBST($root) {
        $this->inorderTraversal($root);
        
        $minDistance = PHP_INT_MAX;
        for ($i = 1; $i < count($this->inorderNodes); $i++) {
            $minDistance = min($minDistance, $this->inorderNodes[$i] - $this->inorderNodes[$i - 1]);
        }
        
        return $minDistance;
    }
}

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

class UnionFind {
    private $parent;

    public function __construct($size) {
        $this->parent = range(0, $size - 1);
    }

    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX != $rootY) {
            $this->parent[$rootX] = $rootY;
        }
    }

    public function connected($x, $y) {
        return $this->find($x) == $this->find($y);
    }
}

class Solution {
    function equationsPossible($equations) {
        $uf = new UnionFind(26);
        
        foreach ($equations as $eq) {
            if ($eq[1] == '=') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                $uf->union($x, $y);
            }
        }
        
        foreach ($equations as $eq) {
            if ($eq[1] == '!') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                if ($uf->connected($x, $y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

function catMouseGame($graph) {
    $n = count($graph);
    $DRAW = 0; $MOUSE = 1; $CAT = 2;
    $dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2, $DRAW)));
    $queue = [];

    for ($i = 1; $i < $n; $i++) {
        $dp[0][$i][0] = $MOUSE;
        $dp[0][$i][1] = $MOUSE;
        $dp[$i][$i][0] = $CAT;
        $dp[$i][$i][1] = $CAT;
        $queue[] = [0, $i, 0, $MOUSE];
        $queue[] = [0, $i, 1, $MOUSE];
        $queue[] = [$i, $i, 0, $CAT];
        $queue[] = [$i, $i, 1, $CAT];
    }

    function parents($graph, $mouse, $cat, $turn) {
        $res = [];
        if ($turn == 1) {
            foreach ($graph[$mouse] as $m) {
                $res[] = [$m, $cat, 0];
            }
        } else {
            foreach ($graph[$cat] as $c) {
                if ($c > 0) $res[] = [$mouse, $c, 1];
            }
        }
        return $res;
    }

    while (!empty($queue)) {
        list($mouse, $cat, $turn, $winner) = array_shift($queue);
        foreach (parents($graph, $mouse, $cat, $turn) as list($m, $c, $t)) {
            if ($dp[$m][$c][$t] == $DRAW) {
                if (($t == 0 && $winner == $MOUSE) || ($t == 1 && $winner == $CAT)) {
                    $dp[$m][$c][$t] = $winner;
                    $queue[] = [$m, $c, $t, $winner];
                } else {
                    $degrees = 0;
                    foreach (parents($graph, $m, $c, $t) as $_) $degrees++;
                    if ($degrees == 0) {
                        $dp[$m][$c][$t] = $winner;
                        $queue[] = [$m, $c, $t, $winner];
                    }
                }
            }
        }
    }

    return $dp[1][2][0];
}

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

class Solution {

    public function merge(&$nums1, $m, $nums2, $n) {
        $nums1Copy = array_slice($nums1, 0, $m);
        $p1 = 0;
        $p2 = 0;
        
        for ($p = 0; $p < $n + $m; $p++) {
            if ($p2 >= $n || ($p1 < $m && $nums1Copy[$p1] <= $nums2[$p2])) {
                $nums1[$p] = $nums1Copy[$p1];
                $p1++;
            } else {
                $nums1[$p] = $nums2[$p2];
                $p2++;
            }
        }
    }
}

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

class CustomFunction {
    public function f($x, $y) {}
}

function findSolution($customfunction, $z) {
    $result = [];
    $x = 1;
    $y = 1000;
    
    while ($x <= 1000 && $y >= 1) {
        $value = $customfunction->f($x, $y);
        if ($value == $z) {
            $result[] = [$x, $y];
            $x++;
        } else if ($value < $z) {
            $x++;
        } else {
            $y--;
        }
    }
    
    return $result;
}

Input: nums = [2,3,0,1,4]
Output: 2

function jump($nums) {
    $answer = 0;
    $n = count($nums);
    $curEnd = 0;
    $curFar = 0;
    for ($i = 0; $i < $n - 1; ++$i) {
        $curFar = max($curFar, $i + $nums[$i]);
        if ($i === $curEnd) {
            ++$answer;
            $curEnd = $curFar;
        }
    }
    return $answer;
}