Question

599. Minimum Index Sum of Two Lists

中文文档

Description

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return _all the common strings with the least index sum_. Return the answer in any order.

 

Example 1:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".

 

Constraints:

• 1 <= list1.length, list2.length <= 1000
• 1 <= list1[i].length, list2[i].length <= 30
• list1[i] and list2[i] consist of spaces ' ' and English letters.
• All the strings of list1 are unique.
• All the strings of list2 are unique.
• There is at least a common string between list1 and list2.

Solutions

Solution 1

class Solution:
  def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
    ans = []
    mp = {v: i for i, v in enumerate(list2)}
    mi = 2000
    for i, v in enumerate(list1):
      if v in mp:
        t = i + mp[v]
        if t < mi:
          mi = t
          ans = [v]
        elif t == mi:
          ans.append(v)
    return ans

class Solution {

  public String[] findRestaurant(String[] list1, String[] list2) {
    Map<String, Integer> mp = new HashMap<>();
    for (int i = 0; i < list2.length; ++i) {
      mp.put(list2[i], i);
    }
    List<String> ans = new ArrayList<>();
    int mi = 2000;
    for (int i = 0; i < list1.length; ++i) {
      if (mp.containsKey(list1[i])) {
        int t = i + mp.get(list1[i]);
        if (t < mi) {
          ans = new ArrayList<>();
          ans.add(list1[i]);
          mi = t;
        } else if (t == mi) {
          ans.add(list1[i]);
        }
      }
    }
    return ans.toArray(new String[0]);
  }
}

class Solution {
public:
  vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
    unordered_map<string, int> mp;
    for (int i = 0; i < list2.size(); ++i) mp[list2[i]] = i;
    int mi = 2000;
    vector<string> ans;
    for (int i = 0; i < list1.size(); ++i) {
      if (mp.count(list1[i])) {
        int t = i + mp[list1[i]];
        if (t < mi) {
          ans.clear();
          ans.push_back(list1[i]);
          mi = t;
        } else if (t == mi) {
          ans.push_back(list1[i]);
        }
      }
    }
    return ans;
  }
};

func findRestaurant(list1 []string, list2 []string) []string {
  mp := make(map[string]int)
  for i, v := range list2 {
    mp[v] = i
  }
  mi := 2000
  var ans []string
  for i, v := range list1 {
    if _, ok := mp[v]; ok {
      t := i + mp[v]
      if t < mi {
        ans = []string{v}
        mi = t
      } else if t == mi {
        ans = append(ans, v)
      }
    }
  }
  return ans
}

function findRestaurant(list1: string[], list2: string[]): string[] {
  let minI = Infinity;
  const res = [];
  const map = new Map<string, number>(list1.map((s, i) => [s, i]));
  list2.forEach((s, i) => {
    if (map.has(s)) {
      const sumI = i + map.get(s);
      if (sumI <= minI) {
        if (sumI < minI) {
          minI = sumI;
          res.length = 0;
        }
        res.push(s);
      }
    }
  });
  return res;
}

use std::collections::HashMap;
use std::iter::FromIterator;

impl Solution {
  pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
    let map: HashMap<String, usize> = HashMap::from_iter(list1.into_iter().zip(0..));
    let mut res = vec![];
    let mut min_i = usize::MAX;
    list2
      .into_iter()
      .enumerate()
      .for_each(|(i, key)| {
        if map.contains_key(&key) {
          let sum_i = map.get(&key).unwrap() + i;
          if sum_i <= min_i {
            if sum_i < min_i {
              min_i = sum_i;
              res.clear();
            }
            res.push(key);
          }
        }
      });
    res
  }
}

Solution 2

func findRestaurant(list1[] string, list2[] string)[] string {
mp:= make(map[string]int)
  for i, v := range list2 {
    mp[v] = i
  }
  mi := 2000
  var ans []string
  for i, v := range list1 {
    if _
      , ok : = mp[v];
    ok {
    t:
      = i + mp[v] if t < mi {
        ans = [] string { v } mi = t
      }
      else if t == mi {
        ans = append(ans, v)
      }
    }
  }
  return ans
}