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).
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.
ac
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
// edge cases
if (list1.length == 0 || list2.length == 0) return new String[0];
if (list1.length < list2.length) return findRestaurant(list2, list1); // save some space
// list2 add to map
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < list2.length; i++) {
map.put(list2[i], i);
}
// iterate list1, get indices sum
List<String> res = new ArrayList<>();
int minSum = Integer.MAX_VALUE;
for (int i = 0; i < list1.length; i++) {
if (map.containsKey(list1[i])) {
int currSum = i + map.get(list1[i]);
if (currSum <= minSum) {
if (currSum < minSum) res = new ArrayList<>(); // reset
res.add(list1[i]);
minSum = currSum;
}
}
}
// list to array
String[] ans = new String[res.size()];
for (int i = 0; i < res.size(); i++) {
ans[i] = res.get(i);
}
return ans;
}
}