[LeetCode] 245. Shortest Word Distance III

csRyan 发布于2019-08-16 14:00 / 1969人阅读

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 in the list.

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “makes”, word2 = “coding”
Output: 1
Input: word1 = "makes", word2 = "makes"
Output: 3
Note:
You may assume word1 and word2 are both in the list.

Solution

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        Map> 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);
        }
        if (word1.equals(word2)) {
            List list = map.get(word1);
            if (list.size() < 2) return -1;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < list.size()-1; i++) {
                min = Math.min(min, list.get(i+1)-list.get(i));
            }
            return min;
        }
        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 line 245 III

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

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

[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] 244. Shortest Word Distance II

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

Nekron 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
[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 PHP题解--D49 821. Shortest Distance to a Ch

摘要：返回字符串中每一个字符离给定的字符的最短距离。否则，当当前下标大于上一个出现字符的位置，且存在下一个字符时，距离为两者中最小的那个。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D49 821. Shortest Distance to a Character 题目链接 821. Shortest Distance to a Character 题目分析给定一个字符串s和一个字符...

Shisui 2019-07-01 12:44 评论0 收藏0