【C++刷题】力扣-#243-最短单词距离

2024/10/24 15:12:23 来源：https://blog.csdn.net/FRF65/article/details/143072565 浏览: 次关键词：【C++刷题】力扣-#243-最短单词距离

题目描述

给定一个单词列表 words 和两个单词 word1 和 word2，返回这两个单词在列表中的最短距离。如果 word1 和 word2 是同一个单词，则返回它与自身的最近距离。

示例

示例 1:

输入: words = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
输出: 1

示例 2:

输入: words = ["practice", "makes", "perfect", "makes"], word1 = "makes", word2 = "makes"
输出: 2

题解

这个问题可以通过遍历数组并跟踪 word1 和 word2 的最近出现位置来解决。

初始化：创建两个变量 index1 和 index2 来存储 word1 和 word2 的索引，并将它们初始化为 -1。同时，创建一个变量 minDistance 来存储最小距离，并将其初始化为 ∞。
遍历数组：遍历单词列表 words。
○ 如果当前单词等于 word1，则更新 index1 为当前索引，并更新 minDistance 为 index1 和 index2 之间的距离。
○ 如果当前单词等于 word2，则更新 index2 为当前索引，并更新 minDistance 为 index1 和 index2 之间的距离。
○ 每次更新 minDistance 时，使用 min(minDistance, abs(index1 - index2)) 来确保它是最小的。
返回结果：遍历结束后，返回 minDistance。

代码实现

int shortestDistance(vector<string>& words, string word1, string word2) {int index1 = -1, index2 = -1;int minDistance = INT_MAX;for (int i = 0; i < words.size(); i++) {if (words[i] == word1) {index1 = i;if (index2 != -1) {minDistance = min(minDistance, abs(index1 - index2));}}if (words[i] == word2) {index2 = i;if (index1 != -1) {minDistance = min(minDistance, abs(index1 - index2));}}}return minDistance;
}