AC Java clean solution


  • 112
    public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1, p2 = -1, min = Integer.MAX_VALUE;
        
        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)
                min = Math.min(min, Math.abs(p1 - p2));
        }
        
        return min;
    }

  • 1

    Great idea! Just one-pass! I rewrite it in C++.

    class Solution {
    public:
        int shortestDistance(vector<string>& words, string word1, string word2) {
            int n = words.size(), idx1 = -1, idx2 = -1, dist = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (words[i] == word1) idx1 = i;
                else if (words[i] == word2) idx2 = i;
                if (idx1 != -1 && idx2 != -1)
                    dist = min(dist, abs(idx1 - idx2));
            }
            return dist;
        }
    }; 

  • 0

    Thanks mate! :)


  • 0
    V

    Great idea. Just if someone like, we can remove the "if (p1 != -1 && p2 != -1)" checking by setting p1 = Integer.MAX_VALUE / 2, p2 = Integer.MIN_VALUE / 2 :)


  • 3
    K

    It will save much time if you only update min when word1 or word2 is met. Otherwise, once both word1 and word2 occurred, min will be updated in each iteration.


  • 0

    I think @kimikowang's suggestion is a good consideration :-)


  • 0
    Z

    vote for clean code! Same idea but my code is not clean as that


  • 0
    E

    Exactly the same answer here :)


  • 0
    S

    A silly question, what's the time complexity for this algorithm?


  • 0
    P

    @steve.j.sun I guess it O(n) where n is length of word array.
    Please correct me?


  • 2
    L
    public class Solution {
        public int shortestDistance(String[] words, String word1, String word2) {
            int pos1 = -1;
            int pos2 = -1;
            int len = Integer.MAX_VALUE;
            int iter = 0;
            boolean changed = false;
            
            for (String word : words) {
                if (word.equals(word1)) {
                    pos1 = iter;
                    changed = true;
                } else if (word.equals(word2)) {
                    pos2 = iter;
                    changed = true;
                }
                if (changed && pos1 != -1 && pos2 != -1) {
                    len = Math.min(Math.abs(pos1 - pos2), len);
                    changed = false;
                }
                iter++;
            }
            return len;
        }
    }
    

    I add a boolean to check if position has changed to save some extra time.


  • 1
    Y

    @lisen
    Great idea. I think we can also check for change without an extra boolean value
    A change can be checked by if((pos1 == i || pos2 == i) && (pos1 != -1 && pos2 != -1)).


  • 8

    @jeantimex You don't need to calculate min every round, because once you find both indexes, you check min even though neither is changed, which is inefficient. Here is my code, please review it.

    public class Solution {
        public int shortestDistance(String[] words, String word1, String word2) {
            Integer index1 = null, index2 = null;
            int res = Integer.MAX_VALUE;
            for(int i = 0; i < words.length; i++) {
                if(words[i].equals(word1)) {
                    index1 = i;
                    if(index2 != null) res = Math.min(res, Math.abs(index1 - index2));
                }
                
                if(words[i].equals(word2)) {
                    index2 = i;
                    if(index1 != null) res = Math.min(res, Math.abs(index1 - index2));
                }
            }
            return res;
        }
    }
    

  • 2
    I

    @xietao0221 you dont need abs, you know i is currently the biggest...


  • 0
    H

    I am sorry if I sound like a newbie. What does a the abbreviation "AC" mean?


  • 1
    X

    @Hack3r AC = Accepted


  • 0
    H

    @xiaojun12 Thanks


  • 1

    C# - You can make this a little simpler. Avoid the -1 checking by initializing your p1 and p2 to negative numbers such that they will not result in the min value. And you don't need Abs function because you know that whatever word you just found will be the greater index. Lastly you may as well make the second if case an else because the words will always be different as stated in the problem.

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

    Here is my solution.

        public int ShortestDistance(string[] words, string word1, string word2) 
        {
            int curr1 = -words.Length;
            int curr2 = -words.Length;
            int min = words.Length;
            for (int i = 0; i < words.Length; i++)
            {
                if (words[i] == word1)
                {
                    curr1 = i;
                    min = curr1 - curr2 < min ? curr1 - curr2 : min;
                }
                else if (words[i] == word2)
                {
                    curr2 = i;
                    min = curr2 - curr1 < min ? curr2 - curr1 : min;
                }
            }
            
            return min;
        }
    

  • 0
    Z

    @jeantimex Excuse me, I have a stupid question. I know it is a two points solution, I am just wondering if this is a greedy solution. I mean is this a greedy method?


  • 0
    R

    Using this solution I made the solution for Shortest Word Distance III. Below is the code

    last_p1 and last_p2 to track last position of the p1 and p2. This variable will be used when word1 and word2 will be similar

    public class Solution {
        public int shortestWordDistance(String[] words, String word1, String word2) {
            int p1 = -1, p2 = -1, last_p1 = -1,last_p2 = -1,min = Integer.MAX_VALUE;
            
            for (int i = 0; i < words.length; i++) {
                if (words[i].equals(word1)){
                    last_p1 = p1;
                    p1 = i;
                }
                    
        
                if (words[i].equals(word2)) {
                    last_p2 = p2; 
                	p2 = i;
                  
                }
                    
                if (p1 != -1 && p2 != -1){
                    if(word1.equals(word2)){
                        if (last_p1 != -1 && last_p2 != -1)
                            min = Math.min(min, Math.min(Math.abs(p2-last_p1), Math.abs(p1-last_p2)));
                    }else{
                        min = Math.min(min, Math.abs(p1 - p2));
                    }
                }
                    
            }
            
            return min;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.