LeetCode 0599. Minimum Index Sum of Two Lists Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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: Hash Table

We use a hash table d to record the strings in list2 and their indices, and a variable mi to record the minimum index sum.

Then, we traverse list1. For each string s, if s appears in list2, we calculate the index i of s in list1 and the index j in list2. If i + j < mi, we update the answer array ans to s and update mi to i + j. If i + j = mi, we add s to the answer array ans.

After traversing, return the answer array ans.

PythonJavaC++GoTypeScriptRust

class Solution: def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]: d = {s: i for i, s in enumerate(list2)} ans = [] mi = inf for i, s in enumerate(list1): if s in d: j = d[s] if i + j < mi: mi = i + j ans = [s] elif i + j == mi: ans.append(s) return ans(code-box)

class Solution { public String[] findRestaurant(String[] list1, String[] list2) { Map<String, Integer> d = new HashMap<>(); for (int i = 0; i < list2.length; ++i) { d.put(list2[i], i); } List<String> ans = new ArrayList<>(); int mi = 1 << 30; for (int i = 0; i < list1.length; ++i) { if (d.containsKey(list1[i])) { int j = d.get(list1[i]); if (i + j < mi) { mi = i + j; ans.clear(); ans.add(list1[i]); } else if (i + j == mi) { ans.add(list1[i]); } } } return ans.toArray(new String[0]); } }(code-box)

class Solution { public: vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) { unordered_map<string, int> d; for (int i = 0; i < list2.size(); ++i) { d[list2[i]] = i; } vector<string> ans; int mi = INT_MAX; for (int i = 0; i < list1.size(); ++i) { if (d.contains(list1[i])) { int j = d[list1[i]]; if (i + j < mi) { mi = i + j; ans.clear(); ans.push_back(list1[i]); } else if (i + j == mi) { ans.push_back(list1[i]); } } } return ans; } };(code-box)

func findRestaurant(list1 []string, list2 []string) []string { d := map[string]int{} for i, s := range list2 { d[s] = i } ans := []string{} mi := 1 << 30 for i, s := range list1 { if j, ok := d[s]; ok { if i+j < mi { mi = i + j ans = []string{s} } else if i+j == mi { ans = append(ans, s) } } } return ans }(code-box)

function findRestaurant(list1: string[], list2: string[]): string[] { const d = new Map<string, number>(list2.map((s, i) => [s, i])); let mi = Infinity; const ans: string[] = []; list1.forEach((s, i) => { if (d.has(s)) { const j = d.get(s)!; if (i + j < mi) { mi = i + j; ans.length = 0; ans.push(s); } else if (i + j === mi) { ans.push(s); } } }); return ans; }(code-box)

use std::collections::HashMap; impl Solution { pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> { let mut d = HashMap::new(); for (i, s) in list2.iter().enumerate() { d.insert(s, i); } let mut ans = Vec::new(); let mut mi = std::i32::MAX; for (i, s) in list1.iter().enumerate() { if let Some(&j) = d.get(s) { if (i as i32 + j as i32) < mi { mi = i as i32 + j as i32; ans = vec![s.clone()]; } else if (i as i32 + j as i32) == mi { ans.push(s.clone()); } } } ans } }(code-box)