Tuesday, August 4, 2015

LeetCode [243] Shortest Word Distance

 243. Shortest Word Distance

Easy

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int n = words.size();
        int p1 = -1, p2 = -1, dist = INT_MAX;
        for(int i=0; i<n; ++i){
            if(words[i]==word1) p1 = i;
            if(words[i]==word2) p2 = i;
            if(p1>=0 && p2>=0)
                dist = min(dist, abs(p1-p2));
        }
        return dist;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int n = words.length, i1 = -1, i2 = -1;
        int minD = n;
        for(int i=0; i<n; ++i){
            if(words[i].equals(word1)) i1 = i;
            if(words[i].equals(word2)) i2 = i;
            if(i1>=0 && i2>=0){
                minD = Math.min(Math.abs(i1-i2), minD);
            }
        }
        return minD;
    }
}

No comments:

Post a Comment