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 <= 10001 <= list1[i].length, list2[i].length <= 30list1[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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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]);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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
}
|
