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] and list2[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.