当前位置:网站首页>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
边栏推荐
- JS bright blind your eyes date selector
- 危机重重下的企业发展,数字化转型到底是不是企业未来救星
- Type declaration of all DOM elements in TS
- 手写promise与async await
- [detailed explanation of Huawei machine test] character statistics and rearrangement
- I want to inquire about how to ensure data consistency when a MySQL transaction updates multiple tables?
- Photoshop plug-in - action related concepts - actions in non loaded execution action files - PS plug-in development
- Niuke: intercepting missiles
- mysql8.0JSON_ Instructions for using contains
- 外盘入金都不是对公转吗,那怎么保障安全?
猜你喜欢
随机推荐
Longest common subsequence dynamic programming
Penetration testing methodology
微帧科技荣获全球云计算大会“云鼎奖”!
我想咨询一下,mysql一个事务对于多张表的更新,怎么保证数据一致性的?
【招聘岗位】基础设施软件开发人员
实现一个博客系统----使用模板引擎技术
Brief introduction of machine learning framework
P1451 求细胞数量/1329:【例8.2】细胞
[recruitment position] Software Engineer (full stack) - public safety direction
Coding devsecops helps financial enterprises run out of digital acceleration
机器学习框架简述
Matrix chain multiplication dynamic programming example
NBA赛事直播超清画质背后:阿里云视频云「窄带高清2.0」技术深度解读
机器学习笔记 - 灰狼优化
市值蒸发超百亿美元,“全球IoT云平台第一股”赴港求生
Mongdb learning notes
GPS原始坐标转百度地图坐标(纯C代码)
Implement a blog system -- using template engine technology
There is a powerful and good-looking language bird editor, which is better than typora and developed by Alibaba
Disjoint Set