599. Minimum Index Sum of Two Lists
Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.
You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.
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 restaurant they both like is "Shogun".
Example 2:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"] Output: ["Shogun"] Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).
Example 3:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Burger King","Tapioca Express","Shogun"] Output: ["KFC","Burger King","Tapioca Express","Shogun"]
Example 4:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KNN","KFC","Burger King","Tapioca Express","Shogun"] Output: ["KFC","Burger King","Tapioca Express","Shogun"]
Example 5:
Input: list1 = ["KFC"], list2 = ["KFC"] Output: ["KFC"]
Constraints:
1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i]
andlist2[i]
consist of spaces' '
and English letters.- All the stings of
list1
are unique. - All the stings of
list2
are unique.
Rust Solution
struct Solution;
use std::collections::HashMap;
use std::usize;
impl Solution {
fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
let mut hm: HashMap<&str, usize> = HashMap::new();
let mut min = usize::MAX;
let mut res: Vec<String> = vec![];
for i in 0..list1.len() {
hm.insert(&list1[i], i);
}
for j in 0..list2.len() {
if let Some(i) = hm.get(list2[j].as_str()) {
let sum = i + j;
if sum < min {
min = sum;
res.clear();
}
if sum == min {
res.push(list2[j].to_string());
}
}
}
res
}
}
#[test]
fn test() {
let list1: Vec<String> = vec_string!["Shogun", "Tapioca Express", "Burger King", "KFC"];
let list2: Vec<String> = vec_string![
"Piatti",
"The Grill at Torrey Pines",
"Hungry Hunter Steakhouse",
"Shogun"
];
let res: Vec<String> = vec_string!["Shogun"];
assert_eq!(Solution::find_restaurant(list1, list2), res);
let list1: Vec<String> = vec_string!["Shogun", "Tapioca Express", "Burger King", "KFC"];
let list2: Vec<String> = vec_string!["KFC", "Shogun", "Burger King"];
let res: Vec<String> = vec_string!["Shogun"];
assert_eq!(Solution::find_restaurant(list1, list2), res);
}
Having problems with this solution? Click here to submit an issue on github.