通过复杂的多维数组迭代（PHP上的Trie数据结构，代码改进）

Question

最近我遇到了一个编码挑战，我不得不在PHP中构建一个简单的trie，我设法使用php和foreach循环来完成它， m对代码本身并不满意（看起来并不像它应该的那样），所以我试图用php的迭代器来实现它。

所以，我有一个复杂的数组（线索），例如：

array(
    'a' => array(), 
    'b' => array(
     'a' => array(
      'c' => array(
       'o' => array(
        'n' => array() 
       ) 
      ) 
     ) 
), 
    'x' => array(
     'x' => array(
       'x' => array() 
     ) 
    ) 
); 

我要检查，如果“培根”这是存储在此线索一句话，过程中找到它应该是通过迭代遍历数组，并检查它是嵌套和存在的每个节点，例如：我需要在根中的元素与键'b'，然后在阵列数组[[b']），我需要检查是否存在数组['b'] ['a']，然后['b'] ['a'] ['c']等等。

使用foreach循环，我可以通过引用传递新数组并通过引用来检查密钥。现在使用一个迭代器似乎我锤炼了一些代码（以及做foreachs php复制数组时，使我认为这个解决方案可能使用比使用迭代器更多的内存）的事实。

因此，代码到现在为止它已经条件完成while循环上不能在该停止（当前数组没有我搜索键）或成功（这是完整的字）：

// OUTSIDE THE LOOP 
$finished = false; 
$string = 'bacon'; 
$string = str_split($string); 
$queue = new SplQueue(); 
// Enqueue all the letters to the queue -> skipping this because it's boring 

// FIRST WHILE LOOP 
$iterator = new ArrayIterator($array); 
$iterator->key(); // No match with queue -> check next key 

// SECOND WHILELOOP 
$iterator->next(); 
$iterator->key(); // Matches with the key I want do dequeue (B), 
$next = new ArrayIterator($array[$iterator->key()]); 
$queue->dequeue(); 

// THIRD WHILE LOOP 
$next->key(); // Match [A] -> create new iterator 
$next = new ArrayIterator($next[$next->key()]); 
$queue->dequeue(); 

// 4TH WHILE LOOP 
$next->key(); // Match [C] -> create new iterator 
$next = new ArrayIterator($next[$next->key()]); 
$queue->dequeue(); 

// 5TH WHILE LOOP 
$next->key(); // Match [O] -> create new iterator 
$next = new ArrayIterator($next[$next->key()]); 
$queue->dequeue(); 

// 5TH WHILE LOOP 
$next->key(); // Match [N] 
$next = new ArrayIterator($next[$next->key()]); 
$queue->dequeue(); // queue empty, throw success 

所以，直到现在，这是我的，但事实上，我在每个循环上创建一个新的ArrayIterator它困扰着我，所以我希望能听到有人对此问题有更好的解决方案。

在此先感谢。

Answer 1

这是使用迭代器解决此问题的一个很好的挑战。尽管我认为迭代器很好，但是它们强迫你用迭代方法思考。尽管对于某些问题没有问题，但对于像您这样描述的任务，使用递归更有意义。

所以，我认为你应该接受@cjohansson的答案。因为它是可读的和可理解的。

但正如这里的概念证明是我的解决方案使用RecursiveIteratorIterator。我们必须扩展这个类，并改变了一点，以满足我们的需要，也能减少不必要的迭代次数：

那么我们可以做如下：

$iterator = new TrieRecursiveIteratorIterator(
    $word, 
    new RecursiveArrayIterator($trie), 
    RecursiveIteratorIterator::SELF_FIRST 
); 

$iterator->testForMatches(); 

在那之后，我们可以问我们$iterator不同的东西，如：

1. 如果找到匹配：$iterator->matchFound();
2. 如果找到完全匹配：$iterator->exactMatchFound();
3. 如果有以给定单词为前缀的单词：$iterator->prefixMatchFound();
4. 获取前缀本身（当发现任何一个匹配的前缀将等于给定的词）：$iterator->getPrefix();
5. 获取以给定单词为前缀的结尾：$iterator->getPrefixed()。

这里是working demo。

所以你可以看到这个实现并不像递归一样简单。虽然我是迭代器和SPL用法的忠实粉丝，但这不是银色的子弹，而应该选择更适合当前需求的工具。

此外，这是超出域名，但我的班级违反Single responsibility principle。为了简单起见，这是故意的。在现实生活中，会有另一个类将使用我们的迭代器作为依赖。

Answer 2

这里为递归算法代码将遍历任何数量的级别：

<?php 
$trie = array(
    'a' => array(), 
    'b' => array(
     'a' => array(
      'c' => array(
       'o' => array(
        'n' => array() 
       ) 
      ) 
     ) 
    ), 
    'x' => array(
     'x' => array(
      'x' => array() 
     ) 
    ) 
); 

/** 
* @param string $word 
* @param array $array 
* @param int [$i = 0] 
*/ 
function findWord($word, $array, $i = 0) 
{ 
    $letter = substr($word, $i, 1); 
    if (isset($array[$letter])) { 
     if ($i == strlen($word) - 1) { 
      return true; 
     } else if ($i < strlen($word)) { 
      return findWord($word, $array[$letter], $i + 1); 
     } 
    } 
    return false; 
} 

if (findWord('bacon', $trie)) { 
    die("Did find word."); 
} else { 
    die("Didn't find word."); 
} 

这里为迭代算法代码将遍历任何数量电平的并且应该是存储器和CPU高效：

<?php 

$trie = array(
    'a' => array(), 
    'b' => array(
     'a' => array(
      'c' => array(
       'o' => array(
        'n' => array() 
       ) 
      ) 
     ) 
    ), 
    'x' => array(
     'x' => array(
      'x' => array() 
     ) 
    ) 
); 

/** 
* @param string $word 
* @param array $array 
*/ 
function findWord($word, $array) 
{ 
    $tmpArray = $array; 
    for ($i = 0; $i < strlen($word); $i++) 
    { 
     $letter = substr($word, $i, 1); 
     if (isset($tmpArray[$letter])) { 
      if ($i == strlen($word) - 1) { 
       return true; 
      } else { 
       $tmpArray = $tmpArray[$letter]; 
      } 
     } else { 
      break; 
     } 
    } 
    return false; 
} 

if (findWord('bacon', $trie)) { 
    die("Did find word."); 
} else { 
    die("Didn't find word."); 
}