Why a O(n^2) preprocessing time while O(1) for shortest not a good idea?

I did the same thing after I got TLE and thought on it for sometime i realized the O(n^2) + O(1) solution is a poor decision any time
n
(the number of words) > the number of timesshortest
method is called. Lets take an example sayn
= 64 andshortest
is called 20 times. Now if we look at the approximate total number of operations in our O(n^2) + O(1) solution we would get 64^2 + 20 = 4116. now if you observe others O(n)+O(n) solution their approximate total number of operations would be 64 + (20 * 64) = 1280.In short O(n^2) + O(1) solution is only better if
shortest
is called n times.

Agree. Actually this is the first thing I did for this problem! Since the problem clearly states that the shortest distance will be called for many times, so it indicates to sacrifice space for time.
Consider if number of shortest(,) is called MUCH more than word.size(), then definitely we should registered the distance for each pair (word1, word2), where just to make sure word1 < word2 for uniqueness.Another way to comprise both space and time is that we still define the hash map for pairs in the class, but do NOT populate in constructor. Every time a shortest(,) is called, check whether its value already registered before searching in word list. This way won't waste a single computation if calls with the same pairs are made, and won't compute a useless distance of a pair if it is never called.

@mlblount45 For this problem, should consider "called many times" as significantly larger than words.size().

@mlblount45 You are absolutely right. But I think the easiest way to put it is that quadric is BAD. If you have implemented something in O(n^2), it is going to bite you. The bottom line is O(nlogn). If you have to implement something in O(n^2), remember to have some safety measures. Otherwise you are out there without pants. O(n^2) is a sweet spot for DoS attack or failure.

Giving TLE  11/12 Test Cases passed, last one giving TLE
HashMap<String, Integer> map1; public ShortestWordDistanceII(String[] words, boolean b) { map1 = new HashMap<>(); for (int i = 0; i < words.length; i++) { for (int j = i + 1; j < words.length; j++) { if (!words[i].equals(words[j])) { String st = ""; if (words[i].compareTo(words[j]) < 0) st = words[i] + words[j]; else st = words[j] + words[i]; if (map1.containsKey(st)) map1.put(st, Math.min(map1.get(st), Math.abs(i  j))); else map1.put(st, Math.abs(i  j)); } } } } public int shortest1(String word1, String word2) { if (word1.compareTo(word2) < 0) return map1.get(word1 + word2); else return map1.get(word2 + word1); }