Problem
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. Your method will be called repeatedly many times with different parameters.
Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
class WordDistance { private Map> map; public WordDistance(String[] words) { map = new HashMap >(); for(int i = 0; i < words.length; i++) { String word = words[i]; if (!map.containsKey(word)) map.put(word, new ArrayList<>()); map.get(word).add(i); } } public int shortest(String word1, String word2) { List list1 = map.get(word1); List list2 = map.get(word2); int min = Integer.MAX_VALUE; int i = 0, j = 0; while (i < list1.size() && j < list2.size()) { int index1 = list1.get(i), index2 = list2.get(j); if (index1 < index2) { min = Math.min(min, index2 - index1); i++; } else { min = Math.min(min, index1 - index2); j++; } } return min; } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/72707.html
摘要:存放過程中的所有集合為所有的結(jié)尾,則順序存放這個(gè)結(jié)尾對(duì)應(yīng)的中的所有存放同一個(gè)循環(huán)的新加入的,在下一個(gè)循環(huán)再依次對(duì)其中元素進(jìn)行進(jìn)一步的把首個(gè)字符串放入新,再將放入,并將鍵值對(duì)放入,進(jìn)行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
摘要:代碼第一次寫入就先不比較第一次寫入就先不比較哈希表法復(fù)雜度時(shí)間空間思路因?yàn)闀?huì)多次調(diào)用,我們不能每次調(diào)用的時(shí)候再把這兩個(gè)單詞的下標(biāo)找出來。我們可以用一個(gè)哈希表,在傳入字符串?dāng)?shù)組時(shí),就把每個(gè)單詞的下標(biāo)找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...
Problem Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. word1 and word2 may be the same and they represent two individual words i...
Problem Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list. Example:Assume that words = [practice, makes, perfect, coding, makes]. In...
摘要:題目鏈接和上一題不一樣的是這道題要求最短的路徑,普通的遍歷和都是可以做的,但是求最短路徑的話還是用。這里相當(dāng)于每個(gè)點(diǎn)有至多條相連,每條的就是到墻之前的長(zhǎng)度。 490. The Maze 題目鏈接:https://leetcode.com/problems... 又是圖的遍歷問題,就是簡(jiǎn)單的遍歷,所以dfs和bfs都可以做,復(fù)雜度也是一樣的。這道題要求球不能停下來,即使碰到destina...
閱讀 2045·2023-04-26 02:23
閱讀 1789·2021-09-03 10:30
閱讀 1351·2019-08-30 15:43
閱讀 1191·2019-08-29 16:29
閱讀 531·2019-08-29 12:28
閱讀 2332·2019-08-26 12:13
閱讀 2169·2019-08-26 12:01
閱讀 2400·2019-08-26 11:56