599 Minimum Index Sum of Two Lists

1. Description

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

 

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 strings of list1 are unique.
• All the strings of list2 are unique.

 

2. Algorithms

To calculate index sum, we have to traverse through one list. While we are traversing, if we find that string in list1 is in list2 too, we then calculate index sum and store it into key : value format which key is index sum and value is string. (We have to store index sum as key, because there are dupliacated index sum between strings.)

 

Let's see when we get list1 = ["happy","sad","good"], list2 = ["sad","happy","good"] as input. Because "happy" is in list2, we can calculate index sum as 0 + 1 = 1. Then we store 1 : ["happy"] into dictionary. "Sad" is in list2 also, we can calculate index sum as 1 + 0 = 1. Because there is index sum already, we append "Sad" to ["happy"].

 

1. Start
2. Declare variable named idxSums with empty dictionary.
3. Calculate length of two input list.
4. If n1 > n2, operate function recursively with interchanged inputs.
5. For index in range(n1),
   1. If string of n1 is in list 2,
      1. Calculate index sum of two list.
      2. If index sum is in idxSums already, append string to value.
      3. Else, Initialize value with [string].
6. Return the value with minimum key.
7. End

.

3. Codes

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # idxSums : dict, This variable will store index sum as key and corresponding string as value.
        idxSums = {} 
        n1, n2 = len(list1), len(list2) 
        
        if n1 > n2 : 
            return self.findRestaurant(list2, list1)
        
        for i in range(n1): 
            string = list1[i]
            if string in list2 : 
                idxSum = i + list2.index(string) 
                if idxSum in idxSums : 
                    idxSums[idxSum].append(string) 
                else : 
                    idxSums[idxSum] = [string]
                    
        return min(idxSums.items(), key = lambda x : x[0])[1]
        
# Faster Code 
class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        name_indices_map = {}
        
        # Update string : index in list1. 
        for i, s in enumerate(list1):
            if (s not in name_indices_map):
                name_indices_map[s] = i
                
            
        # Initialize two variables : res, minsum 
        # res : will store result strings
        # minsum : To update minimum index sum 
        res, minsum = [], 100000
        
        for i, s in enumerate(list2): 
            if (s in name_indices_map): 
                indexsum = i + name_indices_map[s]
                if (indexsum < minsum): 
                    minsum = indexsum
                    res = [s]
                elif (indexsum == minsum): 
                    res.append(s)
        
        return res

 

4. Conclusion