LeetCode 745. 前缀和后缀搜索

Categories:

题目描述
思路分析
1. 解法一：哈希表预处理（推荐）
相似题目

题目描述

✅ 745. 前缀和后缀搜索

思路分析

解法一：哈希表预处理（推荐）

核心思路：

对每个单词枚举所有前缀与后缀组合。

用哈希表记录 prefix#suffix 的最大下标。

查询时直接返回对应值。

复杂度分析：

时间复杂度：O(N * L^2)，其中 N 为单词数，L 为单词长度。

空间复杂度：O(N * L^2)。

import java.util.HashMap;
import java.util.Map;

class WordFilter {
    private final Map<String, Integer> map = new HashMap<>();

    public WordFilter(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int len = word.length();
            for (int p = 0; p <= len; p++) {
                String prefix = word.substring(0, p);
                for (int s = 0; s <= len; s++) {
                    String suffix = word.substring(len - s);
                    map.put(prefix + "#" + suffix, i);
                }
            }
        }
    }

    public int f(String pref, String suff) {
        return map.getOrDefault(pref + "#" + suff, -1);
    }
}

type WordFilter struct {
	mp map[string]int
}

func Constructor(words []string) WordFilter {
	mp := make(map[string]int)
	for i, word := range words {
		lenWord := len(word)
		for p := 0; p <= lenWord; p++ {
			prefix := word[:p]
			for s := 0; s <= lenWord; s++ {
				suffix := word[lenWord-s:]
				mp[prefix+"#"+suffix] = i
			}
		}
	}
	return WordFilter{mp: mp}
}

func (wf *WordFilter) F(pref string, suff string) int {
	if val, ok := wf.mp[pref+"#"+suff]; ok {
		return val
	}
	return -1
}

相似题目

题目	难度	考察点
208. 实现 Trie (前缀树)	中等	字典树
211. 添加与搜索单词 - 数据结构设计	中等	字典树
212. 单词搜索 II	困难	字典树
676. 实现一个魔法字典	中等	字典树
820. 单词的压缩编码	中等	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/16942092