书籍数组中两个字符串的最小距离（5）0924

题目

给定一个字符串数组strs，再给定两个字符串str1和str2，返回再strs中str1与str2的最小距离，如果str1和str2为null，或不在strs中，返回-1。

举例

strs = ["1","3","3","3","2","3","1"] ，str1=“1”，str2=“2”，返回2。

strs=["CD"]，str1=“CD”,str2=“AB”，返回-1。

进阶题目

如果查询发生的次数有很多，如果把每次查询的时间复杂度降为O(1)?

解答

从左到右遍历strs，用变量last1记录最近一次出现的str1的位置，用变量last2记录最近一次出现的str2的位置，如果遍历到str1，那么i-last2的值就是当前的str1和左边最它近的str2之间的距离。如果遍历到str2，那么i-last1的值就是当前的str2和左边最它最近的str1之间的距离。用变量min记录这些距离的最小值即可。

 public static int minDistance(String[] strs, String str1,String str2) {if (str1 == null || str2 == null) {return -1;}if (str1.equals(str2)) {return 0;}int last1 = -1;int last2 = -1;int min = Integer.MAX_VALUE;for (int i = 0; i != strs.length; i++) {if (strs[i].equals(str1)) {min = Math.min(min, last2 == -1 ? min :  i - last2);last1 = i;}if (strs[i].equals(str2)) {min = Math.min(min, last1 == -1 ? min : i - last1);last2 = i;}}return min == Integer.MAX_VALUE? -1 : min;}import java.util.HashMap;
import java.util.Map;/*** 数组中两个字符串的最小距离** @author liuck12* @date 2024-09-24 14:22*/
public class Record {private HashMap<String, HashMap<String, Integer>> record;public Record(String[] strArr) {record = new HashMap<String, HashMap<String, Integer>>();HashMap<String, Integer> indexMap = new HashMap<String, Integer>();for (int i = 0; i != strArr.length; i++) {String curStr = strArr[i];update(indexMap, curStr,i);indexMap.put(strArr[i], i);}}private void update(HashMap<String, Integer> indexMap, String str,int i) {//if (!record.containsKey(str)) {record.put(str, new HashMap<String, Integer>());}HashMap<String, Integer> strMap = record.get(str);for (Map.Entry<String, Integer> lastEntry : indexMap.entrySet()) {// 遍历之前的字符串String key = lastEntry.getKey();// 之前的字符串的索引int index = lastEntry.getValue();// 计算当前字符串与之前字符串的距离if (!key.equals(str)){// 之前的字符串与当前字符串不相等HashMap<String, Integer> lastMap = new HashMap<String, Integer>();int curMin = i - index;//   之前的字符串与当前字符串的距离if (strMap.containsKey(key)){// 如果之前的字符串与当前字符串的距离存在int preMin = strMap.get(key); // 之前的最小距离if (curMin < preMin){ // 如果当前字符串与之前字符串的距离小于之前的最小距离strMap.put(key, curMin);// 更新当前字符串与之前字符串的距离lastMap.put(str, curMin);// 更新之前字符串与当前字符串的距离}}else{// 如果之前的字符串与当前字符串的距离不存在strMap.put(key, curMin);lastMap.put(str, curMin);}}}}public int minDistance(String str1, String str2) {if (str1 == null || str2 == null) {return -1;}if (str1.equals(str2)) {return 0;}if (record.containsKey(str1) && record.get(str1).containsKey(str2)){return record.get(str1).get(str2);}return -1;}
}