Round H 2020 Google Kick Start Friends Problem - Java

Problem

There are N people in the world numbered 1 to N. The i-th person has a distinct name Si that is a string of uppercase English letters.

Two people are friends if and only if there is some letter that appears at least once in each of their names. Any such letter does not need to be at the same position in both names. After all, friendship requires having something in common!

A friendship chain of length n between person A and person B is a sequence of people X1, X2, ..., Xn such that X1 = A, Xn = B, and Xi and Xi+1 are friends, for i=1 to n-1. Note that any two people can have zero or more friendship chains between them.

For each of the given Q pairs of people, can you find the length of the shortest friendship chain between them? If there is no friendship chain between a pair, output -1.

Input

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains the two integers N and Q. The second line contains N strings, which are people's names. The i-th string (starting from 1) is Si. Then, Q lines follow, describing the queries. The i-th of these lines contains the two integers Xi and Yi, which are the indexes (counting starting from 1) of a pair of people in the list of names.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a list of the answers for the Q queries in order, separated by spaces.

Limits

Time limit: 40 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 1 ≤ Q ≤ 5 × 104. Si consists of uppercase English letters, for all i. 1 ≤ length of Si ≤ 20, for all i. All Si are distinct. 1 ≤ Xi
Test Set 1

2 ≤ N ≤ 100.

Test Set 2

103 < N ≤ 5 × 104 in at most 10 cases. 2 ≤ N ≤ 103 in all other cases.

Sample

In Sample Case #1, there are two queries:

In the first query, LIZZIE and KEVIN are friends (because they share the letter E in their names). So, the shortest friendship chain length is 2.
In the second query, LIZZIE and BOHDAN are not friends, but have two possible shortest friendship chains (either via KEVIN or LALIT). So, the shortest friendship chain length is 3. Note that there are other friendship chains as well, but they are longer.

In Sample Case #2, there are two queries:

In the first query, KICK and START are not connected by a chain of friends.

The second query is the same as the first query. Note that queries are not guaranteed to be distinct.

Java Code

import java.util.*; public class Solution{ // static int INF = 0x3f3f3f3f; public static void main(String[] args) { Scanner sc= new Scanner(System.in); int test = sc.nextInt(); for(int t=1; t<=test; t++) { int N = sc.nextInt(); int Q = sc.nextInt(); String S[] = new String[N]; for(int i=0; i<N; i++) { S[i] = sc.next(); } int d[][] = new int[26][26]; for(int[] d1 : d) Arrays.fill(d1, Byte.MAX_VALUE); // Arrays.fill(d1,INF); for(int i=0; i<N; i++) { char c1[] = S[i].toCharArray(); char c2[] = S[i].toCharArray(); for(int j=0; j<S[i].length(); j++) { for(int k=0; k<S[i].length(); k++) { if(c1[j] != c2[k]) d[c1[j] - 'A'][c2[k] - 'A'] =1; } } } for(int k=0; k< 26; ++k) for(int i=0; i < 26; ++i) { if(i == k) continue; for(int j=0; j<26; j++) { if(j ==i || j == k) continue; d[i][j] = Math.min(d[i][j],d[i][k] + d[k][j]); } } int ans = 0; List<Integer> li = new ArrayList<Integer>(); for(int i=1; i<=Q; ++i) { int X = sc.nextInt(); int Y = sc.nextInt(); ans = Byte.MAX_VALUE; // ans = INF; char c1[] = S[X-1].toCharArray(); char c2[] = S[Y-1].toCharArray(); boolean found = false; for(int j=0; j<S[X-1].length(); j++) { for(int k=0; k<S[Y-1].length(); k++) { if(c1[j] == c2[k]) { li.add(2); found = true; break; } ans = Math.min(ans, d[c1[j]-'A'][c2[k]-'A']+2); } if(found) break; } if(!found) li.add(ans == Byte.MAX_VALUE ? -1: ans); // li.add(ans == INF ? -1: ans); } System.out.printf("Case #%d: %s\n",t,li.toString().replace("[", "").replace("]", "").replace(",", "")); } } }

Round H 2020 - Kick Start 2020 Editor. Here you can check whether your code satisfies Time and Space Complexity for the above problem.

Here is the link for Google KickStart Round F 2021 Trash Bins Problem.