745. Prefix and Suffix Search

Problem

Given many words, words[i] has weight i.

Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the word with given prefix and suffix with maximum weight. If no word exists, return -1.

Examples:

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1

Note:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. words[i] and prefix, suffix queries consist of lowercase letters only.

Problem Summary

Given multiple words, the weight of words[i] is i. Design a class WordFilter that implements the function WordFilter.f(String prefix, String suffix). This function returns the maximum weight of a word with prefix prefix and suffix suffix. If there is no such word, return -1.

Solution Ideas

• Implement a WordFilter, which has string matching functionality and can find the index of a string whose prefix and suffix both satisfy the conditions. If it can be found, return the index; otherwise, return -1.
• There are 2 solution ideas for this problem. The first is to preprocess all strings in this WordFilter structure, enumerate all combinations of their prefixes and suffixes, and put them in a map. Then, during matching, you only need to look up the key according to your own defined rule. Initialization time complexity is O(N * L^2), lookup time complexity is O(1), and space complexity is O(N * L^2). Here N is the length of the input string array, and L is the maximum length of the strings in the input string array. The second idea is to directly traverse each index of the string array and match sequentially using the string prefix matching method and suffix matching method. Initialization time complexity is O(1), lookup time complexity is O(N * L), and space complexity is O(1). Here N is the length of the input string array, and L is the maximum length of the strings in the input string array.

Code

package leetcode

import "strings"

// Solution 1: lookup time complexity O(1)
type WordFilter struct {
	words map[string]int
}

func Constructor745(words []string) WordFilter {
	wordsMap := make(map[string]int, len(words)*5)
	for k := 0; k < len(words); k++ {
		for i := 0; i <= 10 && i <= len(words[k]); i++ {
			for j := len(words[k]); 0 <= j && len(words[k])-10 <= j; j-- {
				ps := words[k][:i] + "#" + words[k][j:]
				wordsMap[ps] = k
			}
		}
	}
	return WordFilter{words: wordsMap}
}

func (this *WordFilter) F(prefix string, suffix string) int {
	ps := prefix + "#" + suffix
	if index, ok := this.words[ps]; ok {
		return index
	}
	return -1
}

// Solution 2: lookup time complexity O(N * L)
type WordFilter_ struct {
	input []string
}

func Constructor_745_(words []string) WordFilter_ {
	return WordFilter_{input: words}
}

func (this *WordFilter_) F_(prefix string, suffix string) int {
	for i := len(this.input) - 1; i >= 0; i-- {
		if strings.HasPrefix(this.input[i], prefix) && strings.HasSuffix(this.input[i], suffix) {
			return i
		}
	}
	return -1
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.F(prefix,suffix);
 */