[PHP知识库]单词接龙【php版】

方法1 ，BFS法（单向），通过添加虚拟结点建图
如下图所示，虚线框中便是添加的虚拟结点，由于添加了虚拟结点，最后求出的最短路径要除2,再加上首结点的贡献1，如hit-》hot ,最短路径为2， 但因为虚拟结点的存在，变成 2 / 2 + 1

class Solution {

	private $mpWord2inx = [];
	private $mpIdx2Edge = [];
	private $cntWords = -1;

	/**
	 * BFS法（单向），通过添加虚拟结点建图，将每个单词看作一个点，如果两个单词间可以通过一个字符的变换来互换，则它们
	 * 之间存在一条边
	 * @param String $beginWord
	 * @param String $endWord
	 * @param String[] $wordList
	 * @return Integer
	 */
	function ladderLength($beginWord, $endWord, $wordList) {
		if (count($wordList) == 0) {
			return 0;
		}
		foreach ($wordList as $word) {
			$this->addWord($word);
			$indexWord = $this->mpWord2inx[$word];
			$this->addEdge($word, $indexWord);
		}
		// 如果word本身不在wordList中
		if (!array_key_exists($endWord, $this->mpWord2inx)) {
			return 0;
		}
		// 将beginWord加入
		$this->addWord($beginWord);
		$indexBgn = $this->mpWord2inx[$beginWord];
		$this->addEdge($beginWord, $indexBgn);
		// 存储beginWord 到各个 字符的路径长度
		$roadCnt = array_fill(0, $this->cntWords+1, -1);
		$roadCnt[$indexBgn] = 0;
		$queue = new SplQueue();
		$queue->enqueue($indexBgn);
		$indexEnd = $this->mpWord2inx[$endWord];
		while (!$queue->isEmpty()) {
			$curIdx = $queue->dequeue();
			if ($curIdx == $indexEnd) {
				return $roadCnt[$curIdx] / 2 + 1;
			}
			foreach ($this->mpIdx2Edge[$curIdx] as $idx => $flg) {
				// 说明不是回头路
				if ($roadCnt[$idx] === -1) {
					$roadCnt[$idx] = $roadCnt[$curIdx] + 1;
					$queue->enqueue($idx);
				}
			}
		}
		return 0;
	}

	private function addEdge($word, $index) {
		$this->mpIdx2Edge[$index] = array();
		$strLen = strlen($word);
		while ($strLen-- > 0) {
			$charTemp = $word[$strLen];
			// 将字符换成 xxx*xx形式，如cat换成*at、 c*t、 ca*;
			$word[$strLen] = '*';
			$this->addWord($word);
			$indexNew = $this->mpWord2inx[$word];
			// 表示word与其各种变体之间可以互通
			$this->mpIdx2Edge[$indexNew][$index] = 1;
			$this->mpIdx2Edge[$index][$indexNew] = 1;
			$word[$strLen] = $charTemp;
		}
	}
	/**
	 * 添加字符串与其id的映射
	 * @param $word
	 */
	private function addWord($word) {
		if (!array_key_exists($word, $this->mpWord2inx)) {
			$this->mpWord2inx[$word] = ++$this->cntWords;
		}
	}
}

提交结果如下：