599. Minimum Index Sum of Two Lists

Description

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:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["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).

Note:
The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

Solution

HashMap, time O(n), space O(n)

维护一个List保存当前minIndexSum对应的restaunt们。当遇到更小的minIndexSum时，清空这个list。

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> resToIndex = new HashMap<>();
        for (int i = 0; i < list2.length; ++i) {
            resToIndex.put(list2[i], i);
        }
        
        int minIndexSum = Integer.MAX_VALUE;
        List<String> commonRes = new ArrayList<>();
        
        for (int i = 0; i < list1.length; ++i) {
            Integer j = resToIndex.get(list1[i]);
            if (j != null && i + j <= minIndexSum) {
                if (i + j < minIndexSum) {
                    minIndexSum = i + j;
                    // clear current res list because we've found a miner index sum
                    commonRes.clear();  
                }
                commonRes.add(list1[i]);
            }
        }
     
        return commonRes.toArray(new String[commonRes.size()]);
    }
}