599. 两个列表的最小索引总和
题目描述
给定两个字符串数组 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 <= 10001 <= list1[i].length, list2[i].length <= 30list1[i]和list2[i]由空格' '和英文字母组成。list1的所有字符串都是 唯一 的。list2中的所有字符串都是 唯一 的。
解法
方法一：哈希表
我们用一个哈希表 $\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}$ 即可。
Python3
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
Java
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> d = new HashMap<>();
for (int i = 0; i < list2.length; ++i) {
d.put(list2[i], i);
}
List<String> ans = new ArrayList<>();
int mi = 1 << 30;
for (int i = 0; i < list1.length; ++i) {
if (d.containsKey(list1[i])) {
int j = d.get(list1[i]);
if (i + j < mi) {
mi = i + j;
ans.clear();
ans.add(list1[i]);
} else if (i + j == mi) {
ans.add(list1[i]);
}
}
}
return ans.toArray(new String[0]);
}
}
C++
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> d;
for (int i = 0; i < list2.size(); ++i) {
d[list2[i]] = i;
}
vector<string> ans;
int mi = INT_MAX;
for (int i = 0; i < list1.size(); ++i) {
if (d.contains(list1[i])) {
int j = d[list1[i]];
if (i + j < mi) {
mi = i + j;
ans.clear();
ans.push_back(list1[i]);
} else if (i + j == mi) {
ans.push_back(list1[i]);
}
}
}
return ans;
}
};
Go
func findRestaurant(list1 []string, list2 []string) []string {
d := map[string]int{}
for i, s := range list2 {
d[s] = i
}
ans := []string{}
mi := 1 << 30
for i, s := range list1 {
if j, ok := d[s]; ok {
if i+j < mi {
mi = i + j
ans = []string{s}
} else if i+j == mi {
ans = append(ans, s)
}
}
}
return ans
}
TypeScript
function findRestaurant(list1: string[], list2: string[]): string[] {
const d = new Map<string, number>(list2.map((s, i) => [s, i]));
let mi = Infinity;
const ans: string[] = [];
list1.forEach((s, i) => {
if (d.has(s)) {
const j = d.get(s)!;
if (i + j < mi) {
mi = i + j;
ans.length = 0;
ans.push(s);
} else if (i + j === mi) {
ans.push(s);
}
}
});
return ans;
}
Rust
use std::collections::HashMap;
impl Solution {
pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
let mut d = HashMap::new();
for (i, s) in list2.iter().enumerate() {
d.insert(s, i);
}
let mut ans = Vec::new();
let mut mi = std::i32::MAX;
for (i, s) in list1.iter().enumerate() {
if let Some(&j) = d.get(s) {
if (i as i32 + j as i32) < mi {
mi = i as i32 + j as i32;
ans = vec![s.clone()];
} else if (i as i32 + j as i32) == mi {
ans.push(s.clone());
}
}
}
ans
}
}