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.
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".
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).
In this approach, we compare every string in and by traversing over the whole list for every string chosen from . We make use of a hashmap , which contains elements of the form . Here, refers to the sum of indices of matching elements and refers to the list of matching strings whose indices\' sum equals .\n
Thus, while doing the comparisons, whenever a match between a string at index of and index of is found, we make an entry in the corresponding to the sum , if this entry isn\'t already present. If an entry with this sum already exists, we need to keep a track of all the strings which lead to the same index sum. Thus, we append the current string to the list of strings corresponding to sum .\n
At the end, we traverse over the keys of the and find out the list of strings corresponding to the key reprsenting the minimum sum.\n\n
Time complexity : . Every item of is compared with all the items of . and are the lengths of and respectively. And refers to average string length.\n
Space complexity : . In worst case all items of and are same. In that case, hashmap size grows upto , where refers to average string length.\n
Another method could be to traverse over the various (index sum) values and determine if any such string exists in and such that the sum of its indices in the two lists equals .\n
Now, we know that the value of index sum, could range from 0 to . Here, and refer to the length of lists and respectively. Thus, we choose every value of in ascending order. For every chosen, we iterate over . Suppose, currently the string at index in is being considered. Now, in order for the index sum to be the one corresponding to matching strings in and , the string at index in should match the string at index in , such that .\n
Or, stating in other terms, the string at index in should be equal to the string at index in , such that . Thus, for a particular and (from ), we can directly determine that we need to check the element at index in , instead of traversing over the whole .\n
Doing such checks/comparisons, iterate over all the indices of for every value chosen. Whenver a match occurs between and , we put the matching string in a list .\n
We do the same process of checking the strings for all the values of in ascending order. After completing every iteration over for a particular , we check if the list is empty or not. If it is empty, we need to continue the process with the next value considered. If not, the current gives the required list with minimum index sum. This is because we are already considering the index sum values in ascending order. So, the first list to be found is the required resultant list.\n
The following example depicts the process:\n
Time complexity : . There are two nested loops upto and string comparison takes time. Here, refers to the average string length.\n
Space complexity : . list is used to store the result. Assuming is the length of .\n
We make use of a HashMap to solve the given problem in a different way in this approach. Firstly, we traverse over the whole and create an entry for each element of in a HashMap , of the form . Here, refers to the index of the element, and is the element itself. Thus, we create a mapping from the elements of to their indices.\n
Now, we traverse over . For every element ,, of encountered, we check if the same element already exists as a key in the . If so, it means that the element exists in both and . Thus, we find out the sum of indices corresponding to this element in the two lists, given by . If this is lesser than the minimum sum obtained till now, we update the resultant list to be returned, , with the element as the only entry in it.\n
If the is equal to the minimum sum obtained till now, we put an extra entry corresponding to the element in the list.\n
Below code is inspired by @cloud.runner\n\n
Time complexity : . Every item of is checked in a map of . and are the lengths of and respectively.\n
Space complexity : . hashmap size grows upto , where refers to average string length.\n
Analysis written by: @vinod23\n