[LeetCode] 244. Shortest Word Distance II

Nekron 发布于2019-08-16 14:00 / 1141人阅读

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.

Solution

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;
    }
}

GPU云服务器云服务器 Shortest Distance LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72707.html

[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 评论0 收藏0
[Leetcode] Shortest Word Distance 最短单词间距

摘要：代码第一次写入就先不比较第一次写入就先不比较哈希表法复杂度时间空间思路因为会多次调用，我们不能每次调用的时候再把这两个单词的下标找出来。我们可以用一个哈希表，在传入字符串数组时，就把每个单词的下标找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...

jsliang 2019-08-14 12:48 评论0 收藏0
[LeetCode] 245. Shortest Word Distance III

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...

csRyan 2019-08-16 14:00 评论0 收藏0
[LeetCode] 243. Shortest Word Distance

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...

高胜山 2019-08-16 14:00 评论0 收藏0
490. The Maze && 505. The Maze II

摘要：题目链接和上一题不一样的是这道题要求最短的路径，普通的遍历和都是可以做的，但是求最短路径的话还是用。这里相当于每个点有至多条相连，每条的就是到墙之前的长度。 490. The Maze 题目链接：https://leetcode.com/problems... 又是图的遍历问题，就是简单的遍历，所以dfs和bfs都可以做，复杂度也是一样的。这道题要求球不能停下来，即使碰到destina...

BoYang 2019-08-14 17:27 评论0 收藏0