LeetCodeを1日1題解いてみる (day49)

49日目に取り組んだ問題はこちら！

599. Minimum Index Sum of Two Lists

問題文

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.

僕の回答 (失敗作1)

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        tuple1 = set(list1)
        tuple2 = set(list2)
        result = tuple1 & tuple2
        return list(result)

とりあえず共通を探すだけで、このやり方だと、インデックスの和が最小になるものを探すことが難しそうだった。

僕の回答 (失敗作2)

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        sum_idx = len(list1) + len(list2)
        result = ""
        i = 0
        while sum_idx > i and len(list1) > i:
            j = 0
            while sum_idx > j and len(list2) > j:
                if list1[i] == list2[j] and sum_idx > i + j:
                    result = list1[i]
                    sum_idx = i + j
                j += 1
            i += 1
        return list({result})

この場合だと、インデックスの和が最小の単語が複数ある場合に対応できない。

僕の回答 (成功例)

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        sum_idx = len(list1) + len(list2)
        result = []
        i = 0
        while len(list1) > i:
            j = 0
            while len(list2) > j:
                if list1[i] == list2[j]:
                    if sum_idx > i + j:
                        result = [list1[i]]
                        sum_idx = i + j
                    elif sum_idx == i + j:
                        result.append(list1[i])
                j += 1
            i += 1
        return result

動きはしたが、計算量が多くなって非効率である。

良い回答例

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # list1 の要素を辞書に変換（文字列をキー、インデックスを値として格納）
        index_map = {string: i for i, string in enumerate(list1)}
        min_sum = float('inf')  # 最小インデックス合計（初期値は無限大）
        result = []  # 結果を格納するリスト

        # list2 をループして共通部分を探索
        for j, string in enumerate(list2):
            if string in index_map:
                i = index_map[string]
                index_sum = i + j  # インデックスの合計を計算
                if index_sum < min_sum:
                    # 新しい最小値を見つけたら結果を更新
                    min_sum = index_sum
                    result = [string]
                elif index_sum == min_sum:
                    # 最小値が複数ある場合はリストに追加
                    result.append(string)

        return result

学んだこと

• 辞書は計算量O(1)で見つけることができる

コメント

辞書を使いこなせるようになりたいと思いました。

次の問題はこちら!