題目描述
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
Example
Assume that words=["practice", "makes", "perfect", "coding", "makes"]
Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.
Note
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
分析
這道題洛退，首先是遍歷一遍數(shù)組，我們把出現(xiàn)word1和word2的給定單詞所有出現(xiàn)的位置分別存入兩個(gè)數(shù)組里红淡，然后我們對(duì)這兩個(gè)數(shù)組進(jìn)行兩兩比較更新結(jié)果不狮，代碼如下：
解法1
C++
class Solution {
int shortestDistance(vector<string>& words, string word1, string word2) {
vector<int> idx1, idx2;
int res = INT_MAX;
for (int i = 0; i < words.size(); i++) {
if (words[i] == word1) idx1.push_back(i);
else if (words[i] == word2) idx2.push_back(i);
}
for (int i = 0; i < idx1.size(); ++i) {
for (int j = 0; j < idx2.size(); ++j) {
res = min(res, abs(idx1[i] - idx2[j]));
}
}
return res;
}
}
Swift
func shortestDistance(_ words: [String], word1: String, word2: String) -> Int {
var idx1: [Int] = [Int](), idx2 = [Int]()
var res = Int.max
for i in 0..<words.count {
if words[i] == word1 { idx1.append(i) }
else if words[i] == word2 { idx2.append(i) }
}
for i in 0..<idx1.count {
for j in 0..<idx2.count {
res = min(res, abs(idx1[i] - idx2[j]))
}
}
return res
}
print(shortestDistance(["practice", "makes", "perfect", "coding", "makes"], word1: "makes", word2: "coding"))
解法2
上面的那種方法并不高效，我們其實(shí)需要遍歷一次數(shù)組就可以了在旱，我們用兩個(gè)變量p1, p2初始化為-1摇零，然后我們遍歷數(shù)組，遇到單詞1桶蝎，就將其位置存在p1里驻仅，若遇到單詞2，就將其位置存在p2里登渣，如果此時(shí)p1, p2都不為-1了噪服，那么我們更新結(jié)果，參見(jiàn)代碼如下：
C++
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int p1 = -1, p2 = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1) p1 = i;
else if (words[i] == word2) p2 = i;
if (p1 != -1 && p2 != -1) res = min(res, abs(p1 - p2));
}
return res;
}
};
Swift
func shortestDistance1(_ words: [String], word1: String, word2: String) -> Int {
var idx1: Int = -1, idx2 = -1
var res = Int.max
for i in 0..<words.count {
if words[i] == word1 { idx1 = i}
else if words[i] == word2 { idx2 = i}
if idx1 != -1 && idx2 != -1 {
res = min(res, abs(idx1 - idx2))
}
}
return res
}
print(shortestDistance1(["practice", "makes", "perfect", "coding", "makes"], word1: "coding", word2: "practice"))
// Print "3"
解法3
下面這種方法只用一個(gè)輔助變量idx胜茧，初始化為-1粘优，然后遍歷數(shù)組，如果遇到等于兩個(gè)單詞中的任意一個(gè)的單詞呻顽，我們?cè)诳?code>idx是否為-1雹顺，若不為-1，且指向的單詞和當(dāng)前遍歷到的單詞不同廊遍，我們更新結(jié)果嬉愧，參見(jiàn)代碼如下：
C++
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int idx = -1, res = INT_MAX;
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1 || words[i] == word2) {
if (idx != -1 && words[idx] != words[i]) {
res = min(res, i - idx);
}
idx = i;
}
}
return res;
}
};
Swift
func shortestDistance2(_ words: [String], word1: String, word2: String) -> Int {
var idx = -1
var res = Int.max
for i in 0..<words.count {
if words[i] == word1 || words[i] == word2 {
if idx != -1 && words[i] != words[idx] {
res = min(res, abs(i - idx))
}
idx = i
}
}
return res
}
print(shortestDistance2(["practice", "makes", "perfect", "coding", "makes"], word1: "coding", word2: "practice"))
// Prints "3"
參考資料：
https://leetcode.com/discuss/50234/ac-java-clean-solution
https://leetcode.com/discuss/61820/java-only-need-to-keep-one-index
