当前位置:网站首页>Leetcode: Shortest Word Distance II
Leetcode: Shortest Word Distance II
2022-07-05 14:56:00 【Full stack programmer webmaster】
This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Hash table method
Complexity
Time O(N) Space O(N)
Ideas
Because... Will be called many times , We can't find the subscripts of these two words every time we call . We can use a hash table , When passing in a string array , Use HashMap To store word as well as word stay Array What's in it index. So when the shortest distance method is called , We just need to traverse the subscript list of two words . Specific comparison methods , It's like merge two list, Compare two at a time list The two smallest values , You get a difference . Then remove the smaller one . Because we traverse the input array from front to back , So the subscript list is also orderly .
1 public class WordDistance {
2
3 HashMap<String, ArrayList<Integer>> map;
4
5 public WordDistance(String[] words) {
6 this.map = new HashMap<String, ArrayList<Integer>>();
7 for (int i=0; i<words.length; i++) {
8 String item = words[i];
9 if (map.containsKey(item)) {
10 map.get(item).add(i);
11 }
12 else {
13 ArrayList<Integer> list = new ArrayList<Integer>();
14 list.add(i);
15 map.put(item, list);
16 }
17 }
18 }
19
20 public int shortest(String word1, String word2) {
21 ArrayList<Integer> l1 = map.get(word1);
22 ArrayList<Integer> l2 = map.get(word2);
23 int minDis = Integer.MAX_VALUE;
24 int i=0, j=0;
25 while (i<l1.size() && j<l2.size()) {
26 int p1 = l1.get(i);
27 int p2 = l2.get(j);
28 minDis = Math.min(minDis, Math.abs(p1-p2));
29 if (p1 < p2) i++;
30 else j++;
31 }
32 return minDis;
33 }
34 }
35
36 // Your WordDistance object will be instantiated and called as such:
37 // WordDistance wordDistance = new WordDistance(words);
38 // wordDistance.shortest("word1", "word2");
39 // wordDistance.shortest("anotherWord1", "anotherWord2");
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/109200.html Link to the original text :https://javaforall.cn
边栏推荐
- Share 20 strange JS expressions and see how many correct answers you can get
- Reconnaissance des caractères easycr
- Brief introduction of machine learning framework
- dynamic programming
- Coding devsecops helps financial enterprises run out of digital acceleration
- Longest common subsequence dynamic programming
- 【leetcode周赛总结】LeetCode第 81 场双周赛(6.25)
- easyOCR 字符識別
- 在Pytorch中使用Tensorboard可视化训练过程
- FR练习题目---综合题
猜你喜欢
12 MySQL interview questions that you must chew through to enter Alibaba
Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
【华为机试真题详解】字符统计及重排
实现一个博客系统----使用模板引擎技术
Security analysis of Web Architecture
【NVMe2.0b 14-9】NVMe SR-IOV
机器学习笔记 - 灰狼优化
leetcode:881. 救生艇
用 Go 跑的更快:使用 Golang 为机器学习服务
Section - left closed right open
随机推荐
Strong connection component
Type declaration of all DOM elements in TS
[detailed explanation of Huawei machine test] character statistics and rearrangement
Section - left closed right open
I want to inquire about how to ensure data consistency when a MySQL transaction updates multiple tables?
启牛学堂班主任给的证券账户安全吗?能开户吗?
Pointer operation - C language
Drive brushless DC motor based on Ti drv10970
通过npm 或者 yarn安装依赖时 报错 出现乱码解决方式
Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
APR protocol and defense
Leetcode: Shortest Word Distance II
12 MySQL interview questions that you must chew through to enter Alibaba
maxcompute有没有能查询 表当前存储容量的大小(kb) 的sql?
微帧科技荣获全球云计算大会“云鼎奖”!
easyOCR 字符識別
Visual task scheduling & drag and drop | scalph data integration based on Apache seatunnel
面试突击62:group by 有哪些注意事项?
基于TI DRV10970驱动直流无刷电机
你童年的快乐,都是被它承包了