LeetCode : 243. Shortest Word Distance

[congr]

https://leetcode.com/problems/shortest-word-distance/

[congr]

O(N^2)

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        List<Integer> list1 = new ArrayList();
        List<Integer> list2 = new ArrayList();

        for(int i = 0; i<words.length; i++) {
            if (words[i].equals(word1)) list1.add(i);
            if (words[i].equals(word2)) list2.add(i);
        }

        int shortest = Integer.MAX_VALUE;
        for (int i : list1) {
            for (int j : list2) shortest = Math.min(shortest, Math.abs(i-j));
        }

        return shortest;
    }
}

[congr]

O(N)

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int shortest = Integer.MAX_VALUE;
        int p1 = -1, p2 = -1;

        for(int i = 0; i<words.length; i++) {
            if (words[i].equals(word1)) p1 = i;
            if (words[i].equals(word2)) p2 = i;

            if (p1 != -1 && p2 != -1) // !!!
                shortest = Math.min(shortest, Math.abs(p1-p2));
        }

        return shortest;
    }
}