LeetCode 补充题 183. 前缀匹配的全部字符串
题目描述
给定字符串数组与前缀
prefix，按输入顺序返回所有以该前缀开头的字符串，重复项保留。一次查询，大小写敏感，空前缀匹配所有字符串。
示例 1：
输入：
words = ["app","apple","ape","app"], prefix = "app"
输出：["app","apple","app"]
解释： 保留以app开头的所有项，重复项及原有顺序均保留。
提示：
- 仅执行一次前缀查询，区分大小写。
- 保留输入顺序与重复项。
- 空前缀匹配全部字符串。
题意分析
只有一次前缀查询，直接逐项比较即可；构建字典树并不会省去读取输入的成本。结果要求原顺序和重复项，因此扫描到匹配项时直接追加，不使用集合去重或排序。
解法：单次扫描保留全部前缀匹配
核心思路
[!blue]
对每个
word，检查它的开头是否与prefix完全一致。长度不足的字符串不可能匹配；任意对应字符不同就拒绝，完整匹配才加入结果，大小写按原字符比较。处理任意输入前缀后，结果恰好是其中所有匹配项的原顺序列表。逐项追加使该性质一直成立，重复输入也被逐项保留。
startsWith和HasPrefix已处理空前缀边界：它匹配所有字符串，包括空串。返回列表复用原字符串，不需要复制全部字符内容。
解题步骤
- 按原输入顺序逐个读取字符串。
- 使用 startsWith 或对应前缀比较，命中时直接追加原字符串。
- 返回全部匹配项，空前缀自然匹配全部字符串。
代码实现
class Solution {
public List<String> prefixMatches(String[] words, String prefix) {
List<String> out = new ArrayList<>();
for (String word : words) {
if (word.startsWith(prefix)) {
out.add(word);
}
}
return out;
}
}
import "strings"
func prefixMatches(words []string, prefix string) []string {
out := []string{}
for _, word := range words {
if strings.HasPrefix(word, prefix) {
out = append(out, word)
}
}
return out
}
复杂度分析
- 时间复杂度：$O(n\cdot p+n)$，n为字符串数量、p为前缀长度。
- 空间复杂度：除返回引用列表外额外空间 $O(1)$。
关键点总结
[!green]
只查询一次时，构造 Trie 的成本无法由后续查询摊薄；顺序扫描天然保留顺序与重复项。
易错点总结
[!yellow]
原题startsWith只判断是否存在匹配词，本题返回所有匹配项；本文限定单次查询。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 642. 设计搜索自动补全系统 | 困难 | 该题的扫描解法同样逐个过滤前缀匹配项，再按频次保留前三个候选；本题保留所有匹配项，并维持输入顺序及重复项。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！