How can I solve the Minimum Index Sum of Two Lists problem optimally?

You can solve the problem optimally by scanning list1 and using a hash table to track the indices of its elements, followed by scanning list2 to compute the index sums.

What is the time complexity of the Minimum Index Sum of Two Lists problem?

The time complexity is O(n + m), where n and m are the lengths of list1 and list2, respectively.

Can there be multiple strings with the same index sum in this problem?

Yes, if multiple common strings have the same minimum index sum, all of them should be returned in the result.

How do I handle edge cases for multiple strings with the same index sum?

When encountering multiple strings with the same index sum, make sure to store all such strings and return them in the result.

What is the best approach for solving Minimum Index Sum of Two Lists in an interview?

The best approach is to use a hash table for fast lookups and ensure your solution handles edge cases like multiple strings with the same index sum while maintaining an optimal time complexity.

#599

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

两个列表的最小索引总和

给定两个字符串数组 list1 和 list2 ，找到索引和最小的公共字符串。公共字符串是同时出现在 list1 和 list2 中的字符串。具有最小索引和的公共字符串是指，如果它在 list1[i] 和 list2[j] 中出现，那么 i + j 应该是所有其他公共字符串中的最小…

数组哈希表字符串

题目描述

给定两个字符串数组 list1 和 list2，找到 索引和最小的公共字符串。

公共字符串 是同时出现在 list1 和 list2 中的字符串。

具有 最小索引和的公共字符串 是指，如果它在 list1[i] 和 list2[j] 中出现，那么 i + j 应该是所有其他 公共字符串 中的最小值。

返回所有 具有最小索引和的公共字符串。以 任何顺序 返回答案。

示例 1:

输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 唯一的公共字符串是 “Shogun”。

示例 2:

输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 具有最小索引和的公共字符串是 “Shogun”，它有最小的索引和 = (0 + 1) = 1。

示例 3：

输入：list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
输出：["sad","happy"]
解释：有三个公共字符串：
"happy" 索引和 = (0 + 1) = 1.
"sad" 索引和 = (1 + 0) = 1.
"good" 索引和 = (2 + 2) = 4.
最小索引和的字符串是 "sad" 和 "happy"。

提示:

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
list1 的所有字符串都是唯一的。
list2 中的所有字符串都是唯一的。

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $\textit{d}$ 记录 $\textit{list2}$ 中的字符串和它们的下标，用一个变量 $\textit{mi}$ 记录最小的下标和。

然后遍历 $\textit{list1}$ ，对于每个字符串 $\textit{s}$ ，如果 $\textit{s}$ 在 $\textit{list2}$ 中出现，那么我们计算 $\textit{s}$ 在 $\textit{list1}$ 中的下标 $\textit{i}$ 和在 $\textit{list2}$ 中的下标 $\textit{j}$ ，如果 $\textit{i} + \textit{j} < \textit{mi}$ ，我们就更新答案数组 $\textit{ans}$ 为 $\textit{s}$ ，并且更新 $\textit{mi}$ 为 $\textit{i} + \textit{j}$ ；如果 $\textit{i} + \textit{j} = \textit{mi}$ ，我们就将 $\textit{s}$ 加入答案数组 $\textit{ans}$ 。

遍历结束后，返回答案数组 $\textit{ans}$ 即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        d = {s: i for i, s in enumerate(list2)}
        ans = []
        mi = inf
        for i, s in enumerate(list1):
            if s in d:
                j = d[s]
                if i + j < mi:
                    mi = i + j
                    ans = [s]
                elif i + j == mi:
                    ans.append(s)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding hash table usage for index lookup.
question_mark
Ability to handle edge cases where multiple strings have the same index sum.
question_mark
Proficiency in optimizing solutions with linear complexity.

warning

常见陷阱

外企场景

error
Not considering the possibility of multiple strings having the same index sum.
error
Failure to handle large lists efficiently within time constraints.
error
Incorrectly updating the result list when a new minimum index sum is found.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the common strings with the smallest index sum in sorted order.
arrow_right_alt
Extend the problem to handle case insensitivity when comparing strings.
arrow_right_alt
Modify the problem to return the total minimum index sum, not just the strings.

help

常见问题

外企场景

继续练习

#609 在系统中查找重复文件 #648 单词替换 #522 最长特殊序列 II