Word Distance Finder
严氏北美IT公司面试真题汇总和解答论坛 :: LinkedIn公司面试真题: 注册用户可以看到隐藏题目:2017年下半年上机题,8 9 10三个月的onsite面试真题 :: 数据结构的使用:使用HashMap:ShortestWordDistance系列(也有可能电话面试题)
Page 1 of 1
Word Distance Finder
Map<String, List<Integer>> wordIndex = new HashMap<>();
public WordDistanceFinder (List<String> words) {
for (int i = 0; i < words.size(); i++) {
String curr = words.get(i);
if (!wordIndex.containsKey(curr))
wordIndex.put(curr, new ArrayList<Integer>());
wordIndex.get(curr).add(i);
}
}
public int distance (String wordOne, String wordTwo) {
if (wordOne.equals(wordTwo))
return 0;
List<Integer> indexList1 = wordIndex.get(wordOne);
List<Integer> indexList2 = wordIndex.get(wordTwo);
int index1 = 0, index2 = 0, min = Integer.MAX_VALUE;
while (index1 < indexList1.size() && index2 < indexList2.size()) {
int val1 = indexList1.get(index1), val2 = indexList2.get(index2);
if (val1 < val2) {
min = Math.min(min, val2 - val1);
index1++;
} else {
min = Math.min(min, val1 - val2);
index2++;
}
}
return min;
}
public static void main(String[] args) {
WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
System.out.println(finder.distance("fox", "quick") == 1);
System.out.println(finder.distance("quick", "brown") == 1);
}
public WordDistanceFinder (List<String> words) {
for (int i = 0; i < words.size(); i++) {
String curr = words.get(i);
if (!wordIndex.containsKey(curr))
wordIndex.put(curr, new ArrayList<Integer>());
wordIndex.get(curr).add(i);
}
}
public int distance (String wordOne, String wordTwo) {
if (wordOne.equals(wordTwo))
return 0;
List<Integer> indexList1 = wordIndex.get(wordOne);
List<Integer> indexList2 = wordIndex.get(wordTwo);
int index1 = 0, index2 = 0, min = Integer.MAX_VALUE;
while (index1 < indexList1.size() && index2 < indexList2.size()) {
int val1 = indexList1.get(index1), val2 = indexList2.get(index2);
if (val1 < val2) {
min = Math.min(min, val2 - val1);
index1++;
} else {
min = Math.min(min, val1 - val2);
index2++;
}
}
return min;
}
public static void main(String[] args) {
WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
System.out.println(finder.distance("fox", "quick") == 1);
System.out.println(finder.distance("quick", "brown") == 1);
}
Similar topics
» Shortest Word DistanceII
» Shortest Word DistanceIII
» Word LadderII Each Time Delete每次删除一个字符
» Shortest Word Distance IIDot5
» Word Search I leetcode 原题 amazon onsite特喜欢考
» Shortest Word DistanceIII
» Word LadderII Each Time Delete每次删除一个字符
» Shortest Word Distance IIDot5
» Word Search I leetcode 原题 amazon onsite特喜欢考
严氏北美IT公司面试真题汇总和解答论坛 :: LinkedIn公司面试真题: 注册用户可以看到隐藏题目:2017年下半年上机题,8 9 10三个月的onsite面试真题 :: 数据结构的使用:使用HashMap:ShortestWordDistance系列(也有可能电话面试题)
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|