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"]
.
Input: word1 =“coding”
, word2 =“practice”
Output: 3
Input: word1 ="makes"
, word2 ="coding"
Output: 1
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
把位置记录到2个list里,然后逐个对比即可
class Solution { public: int shortestDistance(vector<string>& words, string word1, string word2) { vector<int> V1; vector<int> V2; for(int i =0;i<words.size();i++){ string ss = words[i]; if(ss==word1){ V1.push_back(i); }else if(ss==word2){ V2.push_back(i); } } int res = INT_MAX; int i2 = 0; for(int i1 = 0;i1<V1.size();i1++){ int a = V1[i1]; int b = V2[i2]; res = min(res, abs(a-b)); if(a>b){ if(i2+1<V2.size()){ i2++; i1--; } } } return res; } };
就是挨个数,根据距离从小到大
************但是这样,两层循环, 太慢,***********
public class Solution { public int shortestDistance(String[] words, String word1, String word2) { int i1=-1,i2=-1; for(int len = 1;len<words.length;len++){ for(int i =0;i+len<words.length;i++){ boolean bln1 = words[i].equals(word1) && words[i+len].equals(word2); boolean bln2 = words[i].equals(word2) && words[i+len].equals(word1); if(bln1 || bln2) return len; } } return -1; } }
Mistakes:
1: 没有注意shortest
No comments:
Post a Comment