Shortest Word Distance – LeetCode 243
Problem
Description
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int n = words.size(), idx1 = -1, idx2 = -1, dist = n;
for (int i = 0; i < n; i++) {
if (words[i] == word1) idx1 = i;
else if (words[i] == word2) idx2 = i;
if (idx1 != -1 && idx2 != -1)
dist = min(dist, abs(idx1 - idx2));
}
return dist;
}
};
|
思路
简单的寻找p1和p2间的最小距离，时间复杂度$O(n)$，空间复杂度$O(1)$。
Better
思路
还没看到更好的思路。