244. Shortest Word Distance II

因为要多次查询，每次都遍历肯定不行，所以要保存信息。

最直接的就是保存每个string出现的位置，查询A,B的时候就直接比较他们所有的出现INDEX中最小的情况。

有一点需要注意的是，A出现的位置和B出现的位置都是按顺序添加的，从小到大。
假设M是A出现的一个位置，N是B出现的一个位置，我们首先更新M和N的距离情况。然后看M和N谁小，小的只有变大才有可能得到更符合要求的结果（距离更小）, 所以只改变当前INDEX小的string，找到它的下一次出现位置。。

public class WordDistance 
{
    Map<String, List<Integer>> map;
    int length;
    public WordDistance(String[] words) 
    {
        length = words.length;
        if(length == 0) return;
        map = new HashMap<String,List<Integer>>();
        
        for(int i = 0; i < words.length;i++)
        {
            if(map.containsKey(words[i]))
            {
                map.get(words[i]).add(i);
            }
            else
            {
                List<Integer> tempList = new ArrayList<>();
                tempList.add(i);
                map.put(words[i],new ArrayList<>(tempList));
            }
        }
    }

    public int shortest(String word1, String word2) 
    {
        
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        
        int l = 0;
        int r = 0;
        int res = Math.abs(list1.get(l) - list2.get(r));
        
        while(l < list1.size() && r < list2.size())
        {
            res = Math.min(res,Math.abs(list1.get(l) - list2.get(r)));
            if(res == 1) return 1;
            
            if(list1.get(l) < list2.get(r)) l++;
            else r++;
            
        }
        
        return res;
  
    }
}

这个题卡了一会……一开始想的是建图。。最短路径，不知道怎么想的。。