Leetcode - Single Number
Leetcode - Shortest Word Distance III

Leetcode - Shortest Word Distance II

violet posted @ Apr 02, 2020 04:40:41 AM in 算法 with tags Algorithm hash Golang merge sort , 297 阅读

https://leetcode.com/problems/shortest-word-distance-ii/

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

 

1. Use a hash to track every word index

2. Find min distance for two arrays. Since the arrays have been sorted, it can use the idea of merge sort to find the minimum distance.

type WordDistance struct {
    wordHash map[string][]int
}


func Constructor(words []string) WordDistance {
    wordHash := map[string][]int{}
    for i, w := range words {
        _, ok := wordHash[w]
        if ok {
            wordHash[w] = append(wordHash[w], i)
        } else {
            wordHash[w] = []int{i}
        }
    }
    return WordDistance{
        wordHash: wordHash,
    }
}


func (this *WordDistance) Shortest(word1 string, word2 string) int {
    arr1 := this.wordHash[word1]
    arr2 := this.wordHash[word2]
    min := math.MaxInt32
    w1Index := 0
    w2Index := 0
    for w1Index < len(arr1) && w2Index < len(arr2) {
        tmp := abs(arr1[w1Index] - arr2[w2Index])
        if tmp < min {
            min = tmp
        }
        if arr1[w1Index] < arr2[w2Index] {
            w1Index++
        } else {
            w2Index++
        }
    }
    return min
}


/**
 * Your WordDistance object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.Shortest(word1,word2);
 */

func abs(a int) int {
    if a < 0 {
        return 0 - a
    }
    return a
}

 

WiFi Name 说:
Feb 09, 2023 12:32:27 AM

Are you getting yourself a new WiFi router, then you might be happy because now you are able to set up your best WiFi names to your liking which is a funny act but a please to do indeed. WiFi Name Well as you already know that the reason why people be objective about finding the best WiFi names for their new connections or routers is that they want some cool or funny names that make them feel nice and at the same time when your friends, family, or someone.

zeus activate 说:
Jul 12, 2023 12:55:10 AM

The Zeus Network is an amazing, fantastic broadcasting distribution service for major entertainment content. It is a top channel that telecasts confidential self-determining information and is a mixer of videos, comedy entertainers, TV dramas, news shows and other entertainment. zeus activate In spite of being a relative newcomer to the commercial streaming sector, Zeus has made a name for itself. Zeus Network allows users to watch all accessible shows offline via a Zeus free trial.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter