PHP：递归地在字母图中查找单词

Question

I'm having a graph like this:

Now, let's say I'm looking for a word CAT. I'm trying to make a nice code to walk this graph and find a word. I'd like it to find all existing positions of a word, not only first one.

The result for $graph->find('cat') should be:

return [
    [1, 0, 6],
    [1, 2, 3]
];

I have created such code in the past, but it was iterative. This time I'd like to try recursive.

Here's what I have so far:

I call it like this:

// LetterGraph is my own class
$graph = new LetterGraph($nodes);
$graph->find('cat');

And in my LetterGraph class I do the following:

public function find(string $word): array {
    $result = [];

    $firstLetter = mb_substr($word, 0, 1);

    foreach ($this->letters as $node) {
        if ($node->letter === $firstLetter) {
            $result[] = $this->walk($word, [$node]);
        }
    }

    return $result;
}

protected function walk(string $word, array $nodes): array {
    $lastNode = end($nodes);

    $letterToFind = mb_substr($word, count($nodes), 1);

    foreach ($lastNode->neighbours as $neighbour) {
        if ($neighbour->letter === $letterToFind) {
            // is return okay here?
            return $this->walk($word, array_merge($nodes, $neighbour);
        }
    }
}

Now, I'm not sure how to deal with recursive returns to make it give me the result I want.

Answer 1

It can be solved using Master theorem. Assuming $node->id is the number you want to see in the resulting array, the recursion may look like

public function find(string $word, array $nodes = null): array
{

    $firstLetter = mb_substr($word, 0, 1);
    $rest = mb_substr($word, 1);

    if (empty($nodes)) {
        //top level call, start to search across all nodes
        $nodes = $this->letters;
    }

    $result = [];

    foreach ($nodes as $node) {
        if ($node->letter === $firstLetter) {
            if (empty($rest)) {
                //exit recursion
                $result[] = [$node->id];
            } else {
                //recursively search rest of the string
                $branches = $this->find($rest, $node->neighbours);
                if (!empty($branches)) {
                    foreach ($branches as $branch) {
                        $result[] = array_merge([$node->id], $branch);
                    }
                }
            }
        }
    }
    return $result;
}