Minimum Index Sum of Two Lists[E,Array,Hash Table,String]

https://leetcode.com/problems/minimum-index-sum-of-two-lists/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.

 

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.

1. C

문자열 비교:

• list1[i] == list2[j]는 문자열 포인터를 비교하는 코드입니다. 하지만 C에서는 문자열의 내용을 비교할 때 strcmp 함수를 사용해야 합니다. 포인터를 비교하는 것은 문자열의 내용을 비교하는 것이 아니며, 따라서 의도한 대로 동작하지 않습니다.

C에서 string을 비교하는 법, 그리고 index를 조정하는 법 등을 배울 수 있는 문제다.

재미는 있다.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** findRestaurant(char** list1, int list1Size, char** list2, int list2Size, int* returnSize) {
    *returnSize = 0;
    int minidx = list1Size+list2Size;
    char** ans = (char**)malloc(minidx*sizeof(char*));
    int idx=0;
    for(int i=0; i<list1Size; i++){
        for(int j=0; j<list2Size; j++){
            if(strcmp(list1[i],list2[j])==0){ //C에서 list 비교방법
                int size = i+j;
                if(size<minidx){
                    idx = 0;
                    minidx = size;
                    ans[idx++] = list1[i];
                    *returnSize = 1;
                }else if(size==minidx){
                (*returnSize)++; // returnSize 괄호 중요
                ans[idx++] = list1[i];
                }
            }
        }
    }
    return ans;
}

 

 

2. C++

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> ans;
        int minval = list1.size() + list2.size();

        for(int i=0;i<list1.size();i++){
            for(int j=0;j<list2.size();j++){
                if(list1[i]==list2[j]){ // found the same things
                    int size = i+j;
                    if(size < minval){
                        minval = size;
                        ans.clear();
                        ans.push_back(list1[i]);
                    }
                    else if(size == minval) ans.push_back(list1[i]);
                }
            }
        }
        return ans;
    }
};

 

3. Python

전체적으로 결은 비슷하다.

 

# Python
class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        min_sum = len(list1) + len(list2) 
        ans = []
        dic = {}
        for i in range(len(list1)):
            dic[list1[i]] = i

        for j in range(len(list2)):
            if list2[j] in dic :
                idx = j + dic[list2[j]]
                if idx < min_sum:
                    min_sum = idx
                    ans = [list2[j]]
                elif idx == min_sum:
                    ans.append(list2[j])
        return ans