Friends Within Three Jumps

Given two array a and b, a[i] and b[i] are friends. And then given two query arrays c and d, find whether c[i] and d[i] are friends within three jumps.(i.e A and B are friends, B and C are friends, so B is a one-jump friend of A and C is a two-jumps friend of A)

• The length of all arrays do not exceed 1000.

• If there is more than one friend relationship chain, calculate the relationship of least jumps.

Have you met this question in a real interview? YesProblem Correction

Example

Given a = [1,2], b = [2,3], c = [1], d = [3], return [1].

Explanation:
1 → 2 → 3 ，3 is a two-jumps friend of 1.

Given a = [1,2,3,4], b = [2,3,4,5], c = [1,1], d = [4,5], return [1,0].

Explanation:
1 → 2 → 3 → 4 → 5，4 is a three-jumps friend of 1, 5 is a four-jumps friend of 1.

时间复杂度不知道

public class Solution {
    /**
     * @param a: The a tuple
     * @param b: The b tuple
     * @param c: the c tuple
     * @param d: the d tuple
     * @return: The answer
     */
    public int[] withinThreeJumps(int[] a, int[] b, int[] c, int[] d) {
        // Write your code here
        
        int[] res = new int[c.length];
        
        
        //n
        for (int i =0; i < c.length ;i++ ){
            if(bfs(c[i],d[i],a,b)){
                res[i] = 1;
            }else{
                res[i] = 0;
            }
        } 
        
        return res;
    }
    
    public boolean bfs(int c, int d, int[] a , int[] b){
        Queue<Integer> queue = new LinkedList<>();
        
        int step = 0;
        queue.offer(c);
        while(!queue.isEmpty() && step < 3 ){
            int size = queue.size();
            
            for(int i = 0; i < size ;i++){
                int num = queue.poll();
                
                //on
                for(int j = 0; j < a.length;j++){
                    if(a[j] == num){
                        if(b[j] == d){
                            return true;
                        }
                        
                        queue.offer(b[j]);
                    }
                    
                    if(b[j] == num){
                        if(a[j] == d){
                            return true;
                        }
                        queue.offer(a[j]);
                    }
                }
            }
            
            step++;
        }
        
        return false;
    }
    
}