当前位置： 面试刷题>> 自动补全 (经典算法题500道)
**题目描述补全**：
题目：实现一个自动补全（Autocomplete）功能，该功能能够接收用户输入的字符串，并基于一个预定义的词汇列表（如字典或数据库中的词汇），返回一系列与用户输入最匹配的词汇列表。要求返回的列表按匹配度排序，最匹配的词汇排在最前面。此外，为了提高性能，需要考虑到大数据量下的效率问题。
**PHP 示例代码**：
```php
children[$char])) {
$node->children[$char] = new TrieNode();
}
$node = $node->children[$char];
}
$node->isEndOfWord = true;
}
$node = $root;
$results = [];
$currentWord = '';
// 遍历Trie树，收集匹配的词汇
for ($i = 0; $i < strlen($input); $i++) {
$char = $input[$i];
if (!isset($node->children[$char])) {
break;
}
$node = $node->children[$char];
$currentWord .= $char;
if ($node->isEndOfWord) {
collectWords($node, $currentWord, $results);
}
}
// 辅助函数：递归收集所有从当前节点开始的单词
function collectWords($node, $prefix, &$results) {
if ($node->isEndOfWord) {
$results[] = $prefix;
}
foreach ($node->children as $char => $childNode) {
collectWords($childNode, $prefix . $char, $results);
}
}
// 根据用户输入排序结果
usort($results, function($a, $b) use ($input) {
$lenA = strpos($a, $input) === false ? PHP_INT_MAX : strpos($a, $input);
$lenB = strpos($b, $input) === false ? PHP_INT_MAX : strpos($b, $input);
return $lenA - $lenB;
});
return array_slice($results, 0, 10); // 返回前10个结果
}
// 示例使用
$words = ["apple", "app", "application", "banana", "code", "coding", "codebase"];
$input = "app";
$results = autocomplete($input, $words);
print_r($results);
?>
```
**Python 示例代码**：
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
def autocomplete(input_str, words):
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def collect_words(node, prefix, results):
if node.is_end_of_word:
results.append(prefix)
for char, child in node.children.items():
collect_words(child, prefix + char, results)
results = []
node = root
current_word = ''
for char in input_str:
if char not in node.children:
break
node = node.children[char]
current_word += char
if node.is_end_of_word:
collect_words(node, current_word, results)
results.sort(key=lambda w: w.startswith(input_str) and (len(w) - len(input_str)) or float('inf'))
return results[:10]
# 示例使用
words = ["apple", "app", "application", "banana", "code", "coding", "codebase"]
input_str = "app"
results = autocomplete(input_str, words)
print(results)
```
**JavaScript 示例代码**：
```javascript
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
function autocomplete(input, words) {
const root = new TrieNode();
words.forEach(word => {
let node = root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
});
function collectWords(node, prefix, results) {
if (node.isEndOfWord) {
results.push(prefix);
}
for (let char in node.children) {
collectWords(node.children[char], prefix + char, results);
}
}
const results = [];
let node = root;
let currentWord = '';
for (let char of input) {
if (!node.children[char]) {
break;
}
node = node.children[char];
currentWord += char;
if (node.isEndOfWord) {
collectWords(node, currentWord, results);
}
}
results.sort((a, b) => {
if (a.startsWith(input) && !b.startsWith(input)) return -1;
if (!a.startsWith(input) && b.startsWith(input)) return 1;
return a.length - b.length;
});
return results.slice(0, 10);
}
// 示例使用
const words = ["apple", "app", "application", "banana", "code", "coding", "codebase"];
const input = "app";
const results = autocomplete(input, words);
console.log(results);
```
以上代码示例展示了如何使用Trie树（前缀树）来实现自动补全功能，并给出了PHP、Python和JavaScript的示例。注意，由于篇幅限制，示例可能未涵盖所有优化和错误处理细节。