当前位置：首页 > article >正文

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

article 2024/10/23 4:44:35

题目描述

给定一个单词列表 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;
}