243/244. Shortest Word Distance I/II

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For 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.

思路: 1. 两个变量idx1, idx2分别用来记录两个word各自的位置,初始都为-1, minDistance为最小距离,初始为words.length; 2.遍历给定的words数组,如果遍历到的word[i]等于word1的话, 获取idx1的位置,如果idx2不为-1的情况下,取distance = |idx2-idx1|; 因为要找一个最小的distance,所以再做个比较; 同理,遍历到的word[i]等于word
2情况下做同样处理。

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        if (word1 == word2 || words == null || words.length == 0) return 0;
        int idx1 = -1, idx2 = -1;
        int minDistance = words.length;
        for(int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                idx1 = i;
                if (idx2 != -1) minDistance = Math.min(minDistance, Math.abs(idx1 - idx2));
            } else if (words[i].equals(word2)) {
                idx2 = i;
                if (idx1 != -1) minDistance = Math.min(minDistance, Math.abs(idx1 - idx2));
            }
        }
        return minDistance;

    }
}

Shortest Word Distance II

思路:问如果call多次怎么办, 很简单加cache!那就用hashmap来实现,注意这里需要定义一个Pair 类来先封装下word1跟word2, 因为word1跟word2是相互的,要生成两个pair实例化对象,所以我们往hashmap里面存的时候要存两次; pair1= new Pair(word1, word2); pair2= new Pair(word2, word1);

public class WordDistance {
    public class Pair {
        String word1;
        String word2;
        public Pair(String word1, String word2) {
            this.word1 = word1;
            this.word2 = word2;
        }
    }

    public HashMap<Pair, Integer> map; 
    public String[] words;

    public WordDistance(String[] words) {
        this.map = new HashMap<>();
        this.words = words;
    }

    public int shortest(String word1, String word2) {
        if (word1 == null || word2 == null || word1.length() == 0 || word2.length() == 0 || word1.equals(word2)) return -1;
        Pair wordPair = new Pair(word1, word2);
        Pair wordPair2 = new Pair(word2, word1);
        if (map.containsKey(wordPair)) {
            return map.get(wordPair);
        } else if (map.containsKey(wordPair2)) {
            return map.get(wordPair2);
        }else {
            int idx1 = -1;
            int idx2 = -1;
            int minDistance = words.length;
            for (int i = 0; i < words.length; i++) {

                if (words[i].equals(word1)) {
                    idx1 = i;
                    if (idx2 != -1) {
                        minDistance = Math.min(minDistance, Math.abs(idx2 - idx1));
                    }
                } else if (words[i].equals(word2)) {
                    idx2 = i;
                    if (idx1 != -1) {
                        minDistance = Math.min(minDistance, Math.abs(idx2 - idx1));
                    }
                }
            }
            map.put(wordPair, minDistance);
            map.put(new Pair(word2, word1), minDistance);
            return minDistance;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s