prefix-and-suffix-search

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the <code>WordFilter</code> class:

<ul>
	<li><code>WordFilter(string[] words)</code> Initializes the object with the <code>words</code> in the dictionary.</li>
	<li><code>f(string pref, string suff)</code> Returns the index of the word in the dictionary, which has the prefix <code>pref</code> and the suffix <code>suff</code>. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return <code>-1</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;WordFilter&quot;, &quot;f&quot;]
[[[&quot;apple&quot;]], [&quot;a&quot;, &quot;e&quot;]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter([&quot;apple&quot;]);
wordFilter.f(&quot;a&quot;, &quot;e&quot;); // return 0, because the word at index 0 has prefix = &quot;a&quot; and suffix = &quot;e&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= words.length &lt;= 104</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 7</code></li>
	<li><code>1 &lt;= pref.length, suff.length &lt;= 7</code></li>
	<li><code>words[i]</code>, <code>pref</code> and <code>suff</code> consist of lowercase English letters only.</li>
	<li>At most <code>104</code> calls will be made to the function <code>f</code>.</li>
</ul>

Prefix and Suffix Search

Design Add and Search Words Data Structure

design-add-and-search-words-data-structure

添加与搜索单词 - 数据结构设计

Design

Trie

Array

Hash Table

String

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 <code>WordFilter</code> 类：

<ul>
	<li><code>WordFilter(string[] words)</code> 使用词典中的单词 <code>words</code> 初始化对象。</li>
	<li><code>f(string pref, string suff)</code> 返回词典中具有前缀&nbsp;<code>pref</code>&nbsp;和后缀 <code>suff</code>&nbsp;的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 <code>-1</code> 。</li>
</ul>

&nbsp;

示例：

<pre>
输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出
[null, 0]
解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suffix = "e" 。
</pre>
&nbsp;

提示：

<ul>
	<li><code>1 &lt;= words.length &lt;= 104</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 7</code></li>
	<li><code>1 &lt;= pref.length, suff.length &lt;= 7</code></li>
	<li><code>words[i]</code>、<code>pref</code> 和 <code>suff</code> 仅由小写英文字母组成</li>
	<li>最多对函数 <code>f</code> 执行 <code>104</code> 次调用</li>
</ul>