当前位置: 面试刷题>> 自动补全 (经典算法题500道)


题目描述补全

题目:实现一个自动补全(Autocomplete)功能,该功能能够接收用户输入的字符串,并基于一个预定义的词汇列表(如字典或数据库中的词汇),返回一系列与用户输入最匹配的词汇列表。要求返回的列表按匹配度排序,最匹配的词汇排在最前面。此外,为了提高性能,需要考虑到大数据量下的效率问题。

PHP 示例代码

<?php

function autocomplete($input, $words) {
    // 使用Trie树(前缀树)可以提高查找效率
    class TrieNode {
        public $children = [];
        public $isEndOfWord = false;
    }

    $root = new TrieNode();
    // 构建Trie树
    foreach ($words as $word) {
        $node = $root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->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 示例代码

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 示例代码

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的示例。注意,由于篇幅限制,示例可能未涵盖所有优化和错误处理细节。

推荐面试题