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

Question

我有这样的图表:

现在，假设我要查找单词 CAT。我正在尝试编写一个很好的代码来遍历这张图并找到一个词。我希望它能找到一个词的所有现有位置，而不仅仅是第一个。

$graph->find('cat') 的结果应该是:

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

我过去曾创建过这样的代码，但它是迭代的。这次我想尝试递归。

这是我目前所拥有的:

我这样调用它:

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

在我的 LetterGraph 类中，我执行以下操作:

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);
        }
    }
}

现在，我不确定如何处理递归返回以使其返回我想要的结果。

Answer 1

可以用Master theorem解决.假设 $node->id 是您希望在结果数组中看到的数字，递归可能看起来像

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;
}