当前位置： 面试刷题>> 单词接龙(经典算法150题)
### 题目描述补充
**单词接龙游戏**
题目要求实现一个单词接龙游戏的算法。在这个游戏中，玩家需要使用一系列单词，其中每个单词的尾字母是下一个单词的首字母（除了第一个单词的首字母和最后一个单词的尾字母外，这两个单词可以特殊处理，比如视为任意匹配）。游戏的目标是找出给定单词列表中所有可能的单词接龙序列。
**输入**：
- 一个字符串数组 `words`，包含所有可用的单词。
- 一个可选的字符串 `startWord` 和 `endWord`，分别表示接龙序列的起始和结束单词（如果未提供，则视为任意单词均可作为起始和结束）。
**输出**：
- 一个二维字符串数组，包含所有可能的单词接龙序列，从 `startWord` 开始到 `endWord` 结束。
**示例**：
输入：
```json
{
"words": ["hit", "cog", "dog", "got", "top", "stop"],
"startWord": "hit",
"endWord": "cog"
}
```
输出：
```json
[
["hit", "top", "cog"],
["hit", "top", "got", "dog", "cog"]
]
```
### PHP 示例代码
```php
function wordChain($words, $startWord, $endWord) {
$result = [];
$wordSet = array_flip($words); // 转换为哈希集合以提高查找效率
$visited = array_fill_keys($words, false); // 标记单词是否已访问
function dfs($path, $currentWord, &$result, &$wordSet, &$visited) {
if ($currentWord === $endWord) {
$result[] = $path;
return;
}
$firstChar = $currentWord[0];
for ($i = 1; $i < strlen($currentWord); $i++) {
$nextChar = $currentWord[$i];
$nextWord = $nextChar . substr($currentWord, 1);
if (isset($wordSet[$nextWord]) && !$visited[$nextWord]) {
$visited[$nextWord] = true;
$path[] = $nextWord;
dfs($path, $nextWord, $result, $wordSet, $visited);
array_pop($path);
$visited[$nextWord] = false;
}
}
}
$visited[$startWord] = true;
$path = [$startWord];
dfs($path, $startWord, $result, $wordSet, $visited);
return $result;
}
// 示例用法
$words = ["hit", "cog", "dog", "got", "top", "stop"];
$startWord = "hit";
$endWord = "cog";
$result = wordChain($words, $startWord, $endWord);
print_r($result);
```
### Python 示例代码
```python
def wordChain(words, startWord, endWord):
word_set = set(words)
result = []
def dfs(path, current_word):
if current_word == endWord:
result.append(path[:])
return
for i in range(1, len(current_word)):
next_word = current_word[i:] + current_word[:i]
if next_word in word_set and next_word not in path:
path.append(next_word)
dfs(path, next_word)
path.pop()
dfs([startWord], startWord)
return result
# 示例用法
words = ["hit", "cog", "dog", "got", "top", "stop"]
startWord = "hit"
endWord = "cog"
result = wordChain(words, startWord, endWord)
print(result)
```
### JavaScript 示例代码
```javascript
function wordChain(words, startWord, endWord) {
const wordSet = new Set(words);
const result = [];
function dfs(path, currentWord) {
if (currentWord === endWord) {
result.push([...path]);
return;
}
for (let i = 1; i < currentWord.length; i++) {
const nextWord = currentWord.slice(i) + currentWord.slice(0, i);
if (wordSet.has(nextWord) && !path.includes(nextWord)) {
path.push(nextWord);
dfs(path, nextWord);
path.pop();
}
}
}
const path = [startWord];
dfs(path, startWord);
return result;
}
// 示例用法
const words = ["hit", "cog", "dog", "got", "top", "stop"];
const startWord = "hit";
const endWord = "cog";
const result = wordChain(words, startWord, endWord);
console.log(result);
```
以上代码均实现了单词接龙游戏的算法，并给出了示例用法。注意，这些代码示例均不包含任何表情符号，并尽量精简地描述了问题及其解决方案。