Question

17.11. Find Closest

中文文档

Description

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. If the operation will be repeated many times for the same file (but different pairs of words), can you optimize your solution?

Example:

Input: words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"

Output: 1

Note:

• words.length <= 100000

Solutions

Solution 1

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

Solution 2

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
}