8/5 每日一題(兩組list中 找出共同字串索引和為最小值的共同字串)

 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.

 

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 common string is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".

 

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.
• There is at least a common string between list1 and list2.

class Solution:

    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:

        i=0

        min_index=10000

        res=[]

        while i < len(list1):

           

            if list1[i] in list2:              

                index_cls=list1.index(list1[i])+list2.index(list1[i])

                if min_index == list1.index(list1[i])+list2.index(list1[i]):

                    #可能同時多個最短索引和                    

                    res.append(list1[i])

                if min_index > min(index_cls,min_index):

                    #檢查是否為最小索引和,如果不同就更新最小值,同時更新公共字串

                    min_index = index_cls

                    res=[list1[i]]              

            i+=1

        return res

-----------------參考解答

class Solution:

    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:

       

        min_index=10000

        res=[]

        list2_dict={}

        for i,k in enumerate(list2):

            list2_dict[k]=i

       

        for i,k in enumerate(list1):

            if k in list2_dict:

                index_2=list2_dict.get(k)

                if min_index == i + index_2:

        #出現相同索引和時res加入新的共同字串

                    res.append(k)

                elif min_index > i + index_2:

        #出現最小值時刷新list_res

  

                    min_index = i + index_2

                    res=[k]

        return res