给定一个字符串集合S,要求快速判断一个字符串T是否为S中某个字符串的前缀,并统计S中以T为前缀的字符串数量,最佳的数据结构选择是?

答案解析

A. 散列表虽然查找效率高,但是无法快速找到具有前缀关系的所有字符串。需要遍历整个散列表才能找到所有以给定字符串为前缀的字符串,效率较低。 B. 平衡树可以维护字符串的字典序,但是查找前缀需要逐字符比较,效率不高,且不支持快速统计数量。 C. 字典树(Trie) 是一种专门用于存储字符串的数据结构,可以快速判断一个字符串是否为集合中某个字符串的前缀,且在字典树的路径上可统计以该前缀为根的子树大小,进而统计出数量,非常适合此场景。 D. 向量是一种动态数组,查找字符串需要遍历,不适合前缀查找。
正确答案:C
随机推荐
开始刷题