当前位置:网站首页>Leetcode daily question (745. prefix and suffix search)
Leetcode daily question (745. prefix and suffix search)
2022-07-03 09:33:00 【wangjun861205】
Design a special dictionary with some words that searchs the words in it by a prefix and a suffix.
Implement the WordFilter class:
WordFilter(string[] words) Initializes the object with the words in the dictionary.
f(string prefix, string suffix) Returns the index of the word in the dictionary, which has the prefix prefix and the suffix suffix. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.
Example 1:
Input
[“WordFilter”, “f”] > [[[“apple”]], [“a”, “e”]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter([“apple”]);
wordFilter.f(“a”, “e”); // return 0, because the word at index 0 has prefix = “a” and suffix = 'e".
Constraints:
- 1 <= words.length <= 15000
- 1 <= words[i].length <= 10
- 1 <= prefix.length, suffix.length <= 10
- words[i], prefix and suffix consist of lower-case English letters only.
- At most 15000 calls will be made to the function f.
Treat each word alphabetically into suffix#prefix Combination form , Then you can query , The time complexity of query is O(1), What we should pay attention to here is , Every suffix#prefix Of key Only need to correspond to one of the largest index Just fine , Because that's what the query requires
use std::collections::HashMap;
struct WordFilter {
m: HashMap<String, i32>,
}
/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */
impl WordFilter {
fn new(words: Vec<String>) -> Self {
let mut m = HashMap::new();
for (i, word) in words.into_iter().enumerate() {
let mut prefix = String::new();
for pc in word.chars() {
prefix.push(pc);
let mut suffix = String::new();
for sc in word.chars().rev() {
suffix.insert(0, sc);
*m.entry(suffix.clone() + "#" + &prefix).or_insert(0) = i as i32;
}
}
}
Self {
m }
}
fn f(&self, prefix: String, suffix: String) -> i32 {
*self.m.get(&(suffix + "#" + &prefix)).unwrap_or(&-1)
}
}
边栏推荐
- Spark 结构化流写入Hudi 实践
- Arduino handles JSON data, arduinojson assistant
- Using Hudi in idea
- 用Redis实现分布式锁
- 307. Range Sum Query - Mutable
- LeetCode每日一题(968. Binary Tree Cameras)
- What do software test engineers do? Pass the technology to test whether there are loopholes in the software program
- PIP configuring domestic sources
- Filter comments to filter out uncommented and default values
- [CSDN] C1 training problem analysis_ Part III_ JS Foundation
猜你喜欢
数字身份验证服务商ADVANCE.AI顺利加入深跨协 推进跨境电商行业可持续性发展
软件测试工程师是做什么的 通过技术测试软件程序中是否有漏洞
[kotlin learning] operator overloading and other conventions -- overloading the conventions of arithmetic operators, comparison operators, sets and intervals
PolyWorks script development learning notes (II) -treeview basic operations
Win10安装ELK
[CSDN]C1训练题解析_第三部分_JS基础
【Kotlin学习】类、对象和接口——定义类继承结构
npm install安装依赖包报错解决方法
[point cloud processing paper crazy reading classic version 13] - adaptive graph revolutionary neural networks
Flink-CDC实践(含实操步骤与截图)
随机推荐
Jenkins learning (III) -- setting scheduled tasks
Detailed steps of windows installation redis
Flink学习笔记(十)Flink容错机制
Filter comments to filter out uncommented and default values
There is no open in default browser option in the right click of the vscade editor
LeetCode每日一题(516. Longest Palindromic Subsequence)
Hudi 集成 Spark 数据分析示例(含代码流程与测试结果)
Integrated use of interlij idea and sonarqube
Usage of pandas to obtain MySQL data
About the configuration of vs2008+rade CATIA v5r22
LeetCode每日一题(2305. Fair Distribution of Cookies)
Crawler career from scratch (I): crawl the photos of my little sister ① (the website has been disabled)
Spark overview
Move anaconda, pycharm and jupyter notebook to mobile hard disk
PolyWorks script development learning notes (II) -treeview basic operations
Idea uses the MVN command to package and report an error, which is not available
Redis learning (I)
Hudi learning notes (III) analysis of core concepts
Jestson Nano自定义根文件系统创建(支持NVIDIA图形库的最小根文件系统)
WARNING: You are using pip ; however. Later, upgrade PIP failed, modulenotfounderror: no module named 'pip‘