Question

面试题 17.11. 单词距离

English Version

题目描述

有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

示例：

输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
输出：1

提示：

• words.length <= 100000

解法

方法一

class Solution:
  def findClosest(self, words: List[str], word1: str, word2: str) -> int:
    i, j, ans = 1e5, -1e5, 1e5
    for k, word in enumerate(words):
      if word == word1:
        i = k
      elif word == word2:
        j = k
      ans = min(ans, abs(i - j))
    return ans

class Solution {
  public int findClosest(String[] words, String word1, String word2) {
    int i = 100000, j = -100000, ans = 100000;
    for (int k = 0; k < words.length; ++k) {
      String word = words[k];
      if (word.equals(word1)) {
        i = k;
      } else if (word.equals(word2)) {
        j = k;
      }
      ans = Math.min(ans, Math.abs(i - j));
    }
    return ans;
  }
}

class Solution {
public:
  int findClosest(vector<string>& words, string word1, string word2) {
    int i = 1e5, j = -1e5, ans = 1e5;
    for (int k = 0; k < words.size(); ++k) {
      string word = words[k];
      if (word == word1)
        i = k;
      else if (word == word2)
        j = k;
      ans = min(ans, abs(i - j));
    }
    return ans;
  }
};

func findClosest(words []string, word1 string, word2 string) int {
  i, j, ans := 100000, -100000, 100000
  for k, word := range words {
    if word == word1 {
      i = k
    } else if word == word2 {
      j = k
    }
    ans = min(ans, abs(i-j))
  }
  return ans
}

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

function findClosest(words: string[], word1: string, word2: string): number {
  let index1 = 100000;
  let index2 = -100000;
  let res = 100000;
  const n = words.length;
  for (let i = 0; i < n; i++) {
    const word = words[i];
    if (word === word1) {
      index1 = i;
    } else if (word === word2) {
      index2 = i;
    }
    res = Math.min(res, Math.abs(index1 - index2));
  }
  return res;
}

impl Solution {
  pub fn find_closest(words: Vec<String>, word1: String, word2: String) -> i32 {
    let mut res = i32::MAX;
    let mut index1 = -1;
    let mut index2 = -1;
    for (i, word) in words.iter().enumerate() {
      let i = i as i32;
      if word.eq(&word1) {
        index1 = i;
      } else if word.eq(&word2) {
        index2 = i;
      }
      if index1 != -1 && index2 != -1 {
        res = res.min((index1 - index2).abs());
      }
    }
    res
  }
}

方法二

class Solution:
  def findClosest(self, words: List[str], word1: str, word2: str) -> int:
    d = defaultdict(list)
    for i, w in enumerate(words):
      d[w].append(i)
    ans = 1e5
    idx1, idx2 = d[word1], d[word2]
    i, j, m, n = 0, 0, len(idx1), len(idx2)
    while i < m and j < n:
      ans = min(ans, abs(idx1[i] - idx2[j]))
      if idx1[i] < idx2[j]:
        i += 1
      else:
        j += 1
    return ans

class Solution {
  public int findClosest(String[] words, String word1, String word2) {
    Map<String, List<Integer>> d = new HashMap<>();
    for (int i = 0; i < words.length; ++i) {
      d.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
    }
    List<Integer> idx1 = d.get(word1), idx2 = d.get(word2);
    int i = 0, j = 0, m = idx1.size(), n = idx2.size();
    int ans = 100000;
    while (i < m && j < n) {
      int t = Math.abs(idx1.get(i) - idx2.get(j));
      ans = Math.min(ans, t);
      if (idx1.get(i) < idx2.get(j)) {
        ++i;
      } else {
        ++j;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int findClosest(vector<string>& words, string word1, string word2) {
    unordered_map<string, vector<int>> d;
    for (int i = 0; i < words.size(); ++i) d[words[i]].push_back(i);
    vector<int> idx1 = d[word1], idx2 = d[word2];
    int i = 0, j = 0, m = idx1.size(), n = idx2.size();
    int ans = 1e5;
    while (i < m && j < n) {
      int t = abs(idx1[i] - idx2[j]);
      ans = min(ans, t);
      if (idx1[i] < idx2[j])
        ++i;
      else
        ++j;
    }
    return ans;
  }
};

func findClosest(words []string, word1 string, word2 string) int {
  d := map[string][]int{}
  for i, w := range words {
    d[w] = append(d[w], i)
  }
  idx1, idx2 := d[word1], d[word2]
  i, j, m, n := 0, 0, len(idx1), len(idx2)
  ans := 100000
  for i < m && j < n {
    t := abs(idx1[i] - idx2[j])
    if t < ans {
      ans = t
    }
    if idx1[i] < idx2[j] {
      i++
    } else {
      j++
    }
  }
  return ans
}

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