当前位置:网站首页>Leetcode: Shortest Word Distance II
Leetcode: Shortest Word Distance II
2022-07-05 14:46:00 【全栈程序员站长】
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.
哈希表法
复杂度
时间 O(N) 空间 O(N)
思路
因为会多次调用,我们不能每次调用的时候再把这两个单词的下标找出来。我们可以用一个哈希表,在传入字符串数组时,使用HashMap来储存word以及word在Array里面出现的index。这样当调用最短距离的方法时,我们只要遍历两个单词的下标列表就行了。具体的比较方法,则类似merge two list,每次比较两个list最小的两个值,得到一个差值。然后把较小的那个给去掉。因为我们遍历输入数组时是从前往后的,所以下标列表也是有序的。
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");
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/109200.html原文链接:https://javaforall.cn
边栏推荐
- CPU设计实战-第四章实践任务二用阻塞技术解决相关引发的冲突
- 黑马程序员-软件测试-10阶段2-linux和数据库-44-57为什么学习数据库,数据库分类关系型数据库的说明Navicat操作数据的说明,Navicat操作数据库连接说明,Navicat的基本使用,
- Online electronic component purchasing Mall: break the problem of information asymmetry in the purchasing process, and enable enterprises to effectively coordinate management
- 【学习笔记】阶段测试1
- CPU design related notes
- 家用电器行业商业供应链协同平台解决方案:供应链系统管理精益化,助推企业智造升级
- 开挖财上的证券账户可以吗?安全吗?
- Security analysis of Web Architecture
- 周大福践行「百周年承诺」,真诚服务推动绿色环保
- dynamic programming
猜你喜欢
729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "
【NVMe2.0b 14-9】NVMe SR-IOV
MongDB学习笔记
Thymeleaf 使用后台自定义工具类处理文本
Chow Tai Fook fulfills the "centenary commitment" and sincerely serves to promote green environmental protection
黑马程序员-软件测试-10阶段2-linux和数据库-44-57为什么学习数据库,数据库分类关系型数据库的说明Navicat操作数据的说明,Navicat操作数据库连接说明,Navicat的基本使用,
快消品行业SaaS多租户解决方案,构建全产业链数字化营销竞争力
乌卡时代下,企业供应链管理体系的应对策略
Change multiple file names with one click
[detailed explanation of Huawei machine test] character statistics and rearrangement
随机推荐
mysql8.0JSON_CONTAINS的使用说明
网上电子元器件采购商城:打破采购环节信息不对称难题,赋能企业高效协同管理
Topology可视化绘图引擎
729. My schedule I: "simulation" & "line segment tree (dynamic open point) &" block + bit operation (bucket Division) "
CyCa children's physical etiquette Ningbo training results assessment came to a successful conclusion
微帧科技荣获全球云计算大会“云鼎奖”!
注意!软件供应链安全挑战持续升级
CODING DevSecOps 助力金融企业跑出数字加速度
周大福践行「百周年承诺」,真诚服务推动绿色环保
Thymeleaf common functions
Reconnaissance des caractères easycr
FR练习题目---综合题
Loop invariant
How to solve the problem of garbled code when installing dependency through NPM or yarn
Share 20 strange JS expressions and see how many correct answers you can get
Install and configure Jenkins
Is the securities account given by the head teacher of qiniu school safe? Can I open an account?
Photoshop plug-in action related concepts actionlist actiondescriptor actionlist action execution load call delete PS plug-in development
APR protocol and defense
【jvm】运算指令