Question

244. Shortest Word Distance II

中文文档

Description

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

• WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
• int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

 

Example 1:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");  // return 1

 

Constraints:

• 1 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2
• At most 5000 calls will be made to shortest.

Solutions

Solution 1

class WordDistance:
  def __init__(self, wordsDict: List[str]):
    self.d = defaultdict(list)
    for i, w in enumerate(wordsDict):
      self.d[w].append(i)

  def shortest(self, word1: str, word2: str) -> int:
    a, b = self.d[word1], self.d[word2]
    ans = inf
    i = j = 0
    while i < len(a) and j < len(b):
      ans = min(ans, abs(a[i] - b[j]))
      if a[i] <= b[j]:
        i += 1
      else:
        j += 1
    return ans


# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(wordsDict)
# param_1 = obj.shortest(word1,word2)

class WordDistance {
  private Map<String, List<Integer>> d = new HashMap<>();

  public WordDistance(String[] wordsDict) {
    for (int i = 0; i < wordsDict.length; ++i) {
      d.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
    }
  }

  public int shortest(String word1, String word2) {
    List<Integer> a = d.get(word1), b = d.get(word2);
    int ans = 0x3f3f3f3f;
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
      ans = Math.min(ans, Math.abs(a.get(i) - b.get(j)));
      if (a.get(i) <= b.get(j)) {
        ++i;
      } else {
        ++j;
      }
    }
    return ans;
  }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.shortest(word1,word2);
 */

class WordDistance {
public:
  WordDistance(vector<string>& wordsDict) {
    for (int i = 0; i < wordsDict.size(); ++i) {
      d[wordsDict[i]].push_back(i);
    }
  }

  int shortest(string word1, string word2) {
    auto a = d[word1], b = d[word2];
    int i = 0, j = 0;
    int ans = INT_MAX;
    while (i < a.size() && j < b.size()) {
      ans = min(ans, abs(a[i] - b[j]));
      if (a[i] <= b[j]) {
        ++i;
      } else {
        ++j;
      }
    }
    return ans;
  }

private:
  unordered_map<string, vector<int>> d;
};

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance* obj = new WordDistance(wordsDict);
 * int param_1 = obj->shortest(word1,word2);
 */

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

func Constructor(wordsDict []string) WordDistance {
  d := map[string][]int{}
  for i, w := range wordsDict {
    d[w] = append(d[w], i)
  }
  return WordDistance{d}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
  a, b := this.d[word1], this.d[word2]
  ans := 0x3f3f3f3f
  i, j := 0, 0
  for i < len(a) && j < len(b) {
    ans = min(ans, abs(a[i]-b[j]))
    if a[i] <= b[j] {
      i++
    } else {
      j++
    }
  }
  return ans
}

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

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