Easy

题目描述

给定两个字符串数组 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 的所有字符串都是唯一的
  • list1 和 list2 之间至少有一个公共字符串

解题思路

这道题的核心思路是找到两个数组中的公共字符串，并计算它们的索引总和，最终返回索引总和最小的所有字符串。

解法一：哈希表 + 一次遍历

  1. 用哈希表记录 list1 中每个字符串及其索引
  2. 遍历 list2，如果字符串在哈希表中存在，说明是公共字符串
  3. 计算索引总和，维护最小索引总和和对应的结果列表
  4. 如果发现更小的索引总和，更新结果；如果索引总和相等，添加到结果中

解法二：双层循环暴力匹配 直接用双层循环遍历两个数组，找到相同字符串并计算索引总和。时间复杂度较高，不推荐。

推荐解法一，时间复杂度更优，代码简洁清晰。通过哈希表避免了重复遍历，只需要一次遍历 list1 建立映射，一次遍历 list2 查找匹配。

这种方法的关键在于及时更新最小索引总和，当发现更小的索引总和时清空结果列表重新开始，当索引总和相等时添加到结果中。

代码实现

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> map1;
        for (int i = 0; i < list1.size(); i++) {
            map1[list1[i]] = i;
        }
        
        vector<string> result;
        int minSum = INT_MAX;
        
        for (int i = 0; i < list2.size(); i++) {
            if (map1.count(list2[i])) {
                int sum = i + map1[list2[i]];
                if (sum < minSum) {
                    minSum = sum;
                    result.clear();
                    result.push_back(list2[i]);
                } else if (sum == minSum) {
                    result.push_back(list2[i]);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        map1 = {restaurant: i for i, restaurant in enumerate(list1)}
        
        result = []
        min_sum = float('inf')
        
        for i, restaurant in enumerate(list2):
            if restaurant in map1:
                index_sum = i + map1[restaurant]
                if index_sum < min_sum:
                    min_sum = index_sum
                    result = [restaurant]
                elif index_sum == min_sum:
                    result.append(restaurant)
        
        return result

public class Solution {
    public string[] FindRestaurant(string[] list1, string[] list2) {
        Dictionary<string, int> map1 = new Dictionary<string, int>();
        for (int i = 0; i < list1.Length; i++) {
            map1[list1[i]] = i;
        }
        
        List<string> result = new List<string>();
        int minSum = int.MaxValue;
        
        for (int i = 0; i < list2.Length; i++) {
            if (map1.ContainsKey(list2[i])) {
                int sum = i + map1[list2[i]];
                if (sum < minSum) {
                    minSum = sum;
                    result.Clear();
                    result.Add(list2[i]);
                } else if (sum == minSum) {
                    result.Add(list2[i]);
                }
            }
        }
        
        return result.ToArray();
    }
}

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function(list1, list2) {
    const map1 = new Map();
    for (let i = 0; i < list1.length; i++) {
        map1.set(list1[i], i);
    }
    
    let minSum = Infinity;
    const result = [];
    
    for (let j = 0; j < list2.length; j++) {
        if (map1.has(list2[j])) {
            const indexSum = map1.get(list2[j]) + j;
            if (indexSum < minSum) {
                minSum = indexSum;
                result.length = 0;
                result.push(list2[j]);
            } else if (indexSum === minSum) {
                result.push(list2[j]);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度推荐解法（哈希表）暴力解法
时间复杂度O(m + n)O(m × n)
空间复杂度O(m)O(1)

其中 m 是 list1 的长度，n 是 list2 的长度。

相关题目