244. Shortest Word Distance II 实现数组中的最短距离单词

［抄题］：

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. Your method will be called repeatedly many times with different parameters. 

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3

Input: word1 = "makes", word2 = "coding"
Output: 1

 [暴力解法]：

时间分析：

空间分析：

 [优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

以为实现就是抄一遍：并非，往往需要用其它的数据结构

［英文数据结构或算法，为什么不用别的数据结构或算法］：

前向指针-右移窗口-字符串型。

［一句话思路］：

为了使得窗口尽量小，把窗口左边界往左移 (i j中较小的++)

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

1. 既然是对index进行操作，就要从index的list里面再取一次index
2. 求最小值时一般把result初始化为INT.MAX

［二刷］：

［三刷］：

［四刷］：

［五刷］：

  [五分钟肉眼debug的结果]：

［总结］：

不是while循环一直往右的，就是if条件下 较小的指针往右移就行了

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/递归/分治/贪心］：

［关键模板化代码］：

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

 [代码风格] ：

 [是否头一次写此类driver funcion的代码] ：

实现类的题，类名和主函数名要相同。主函数有参数，新建类就要带参数。

在调用类里正常输入、输出变量就行了。

 

// package whatever; // don't place package name!

import java.io.*;
import java.util.*;
import java.lang.*;


class Solution {
    //ini: hashmap
    HashMap<String, List<Integer>> map = new HashMap<>();
    //require the same signature, initialize with parameter if necessary
    public Solution(String[] words) {
        //store the words
        for (int i = 0; i < words.length; i++) {
            //contains key or not
            if (map.containsKey(words[i])) {
                map.get(words[i]).add(i);
            }else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(words[i], list);
            }
        }
    }
    
    public int shortest(String word1, String word2) {
        //get list1, list2
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        int result = Integer.MAX_VALUE;
        
        //for loop, maintain a sliding window
        for (int i = 0, j = 0; i < list1.size() && j < list2.size();) {
            int index1 = list1.get(i); 
            int index2 = list2.get(j); 
            //minimum the difference
            if (index1 < index2) {
                result = Math.min(result, index2 - index1);
                i++;
            }
            else {
                result = Math.min(result, index1 - index2);
                j++;
            }
        }
        
        //return
        return result;
    }
}

class MyCode {
  public static void main (String[] args) {
    String[] words = {"practice","makes","perfect","coding","makes"};
    Solution answer = new Solution(words);
    String word1 = "practice";
    String word2 = "practice";
    int rst = answer.shortest(word1,word2);
    System.out.println("rst= " + rst);
    
    /*int[] copy = answer.reset();
    for (int i = 0; i < 8; i++)
    System.out.println("copy[i] = " + copy[i]);*/
  }
}

 

 [潜台词] ：