Monday, December 28, 2015

243. Shortest Word Distance ----E

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.

A:
把位置记录到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