244 SWD II

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and 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.

分析

实现一个class，能够利用数组words构造对象：

WordDistance wd = new WordDistance(words);

并实现可以运用上对象的方法，以求最短距离：

int shortestDis = wd.shortest(word1, word2);

与243的区别： 该题含有OOP的思想

思路1

设计class得考虑的问题：

• private variable（fields）
• constructor
• methods

1.private variable

private String[] words;

2.constructor

this.words = words;

3.method: shortest(String word1, String word2)

求最短距离的方法具体实现类似于243

思路1具体实现遇到的问题

1.ArrayList 的排序方法

Collections.sort(AL);

2.代码结果正确但Time limit exceeded

public class WordDistance {

    /*///////////ArrayList////////////
    //fields
    private String[] words;

    //constructor
    public WordDistance(String[] words) {
        this.words = words; 
    }


    //method
    public int shortest(String word1, String word2) {

        int dis = 0;

        //find word1 & word2 's index
        ArrayList<Integer> word1Pos = new ArrayList<Integer>();
        word1Pos = findPos(word1);
        ArrayList<Integer> word2Pos = new ArrayList<Integer>();
        word2Pos = findPos(word2);

        //find shortest distance
        //1.find all possible distance
        ArrayList<Integer> disAL = new ArrayList<Integer>();
        for(int i=0; i < word1Pos.size(); i++) {
            for(int j=0; j < word2Pos.size(); j++) {
                disAL.add(Math.abs(word1Pos.get(i) - word2Pos.get(j)));
            }
        }
        //2.find shortest
        Collections.sort(disAL);
        dis = disAL.get(0);

        return dis;

    }

    private ArrayList<Integer> findPos(String word) {
        ArrayList<Integer> wordPos = new ArrayList<Integer>();
        for(int i=0; i < words.length; i++) {
            if(word.equals(words[i])) {
                wordPos.add(i);
            }
        }
        return wordPos;
    }
}

思路2：将ArrayList换成Array

思路2具体实现遇到的问题：

1.各数组的初始化长度

int[] wordPos = new int[words.length-1];
int[] disA = new int[(words.length-1)*(words.lenght-1)];

2.java平方函数

import java.util.*;
Math.pow(i, 2);

3.数组初始化是0，因此求完wordPos后无法确定数组中0的含义是否是真实的index信息

结论：思路破产

思路3：利用Hashmap

分析： 之前的思路由于每一次运用method都会重新查找wordPos信息，所以当调用许多次method就会导致很耗时，因此如果在创建对象的时候直接生成wordPos的Hashmap，之后的信息这可以直接使用。

1.comstructor

1)创建对象的时候就构建一个hashmap，key是string，value是对应string在数组words中的index。

2)由于每个word对应的index不止一个，因此hashmap的value为ArrayList

2.private variables

private HashMap<String, ArrayList<Integer>> wordPos = new HashMap<String, ArrayList<Integer>>();

3.method

类似思路1

思路3实现中遇到的问题

1.HashMap 的一些操作

containsKey(Object key)
put(K key, V value)
get(Object key)

2.constructor中如何构建HashMap

利用containsKey来看Map中有没有对应的key，如果有，用get取出对应ArrayList的地址，再利用add加入index；如果没有，先用put来给key连上一个ArrayList的对象，用get取出对应ArrayList的地址，再利用add加入index。

Accepted Code

//jiayuanh_0128: 25ms, Your runtime beats 14.50% of java submissions.
////////HashMap/////////
//fields
private HashMap<String, ArrayList<Integer>> wordPosHM = new HashMap<String, ArrayList<Integer>>();

//constructor
public WordDistance(String[] words) {
    for(int i=0; i< words.length; i++) {
        if(wordPosHM.containsKey(words[i])) {
            wordPosHM.get(words[i]).add(i);
        }
        else {
            wordPosHM.put(words[i], new ArrayList<Integer>());
            wordPosHM.get(words[i]).add(i);
        }
    }
}

//method
public int shortest(String word1, String word2) {
    int dis=0;

    //find word1 & word2 's index
    ArrayList<Integer> word1Pos = wordPosHM.get(word1);
    ArrayList<Integer> word2Pos = wordPosHM.get(word2);

    //find shortest distance
    //1.find all possible distance
    ArrayList<Integer> disAL = new ArrayList<Integer>();
    for(int i=0; i < word1Pos.size(); i++) {
        for(int j=0; j < word2Pos.size(); j++) {
            disAL.add(Math.abs(word1Pos.get(i) - word2Pos.get(j)));
        }
    }
    //2.find shortest
    Collections.sort(disAL);
    dis = disAL.get(0);

    return dis;
}