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.
解法一：
public class Solution { public int shortestDistance(String[] words, String word1, String word2) { int idx1=-1; int idx2=-1; int min=Integer.MAX_VALUE; for(int i=0;i<words.length;i++) { if(words[i].equals(word1)) { idx1=i; if(idx2!=-1)min=Math.min(min,idx1-idx2); } if(words[i].equals(word2)) { idx2=i; if(idx1!=-1)min=Math.min(min,idx2-idx1); } } return min; } }
解法二：
hashtable
public class Solution { public int shortestDistance(String[] words, String word1, String word2) { HashMap<String, ArrayList<Integer>> map = new HashMap<String,ArrayList<Integer>>(); for(int i=0;i<words.length;i++) { String word = words[i]; if(!map.containsKey(word)) { map.put(word,new ArrayList<Integer>()); } map.get(word).add(i); } ArrayList<Integer> list1 = map.get(word1); ArrayList<Integer> list2 = map.get(word2); int i = 0; int j = 0; int min = words.length-1; while(i<list1.size()&&j<list2.size()) { int index1 = list1.get(i); int index2 = list2.get(j); min = Math.min(Math.abs(index1-index2),min); if(index1<index2) { i++; } else { j++; } } return min; } }
转载于:https://www.cnblogs.com/hygeia/p/5700010.html
相关资源：JAVA上百实例源码以及开源项目