## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Sharing is caring!

Problem statement
There are $N$ users registered on a website CuteKittens.com. Each of them have a unique password represented by $pass, pass, \dots, pass[N]$. As this a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin don’t want this site to be available for general public. So only those people with passwords can access it.

Yu being an awesome hacker finds a loophole in their password verification system. A string which is concatenation of one or more passwords, in any order, is also accepted by the password verification system. Any password can appear 0 or more times in that string. He has access to each of the $N$ passwords, and also have a string loginAttempt, he has to tell whether this string be accepted by the password verification system of the website.

For example, if there are $3$ users with password {abra, ka, dabra}, then some of the valid combinations are abra ( $pass$), kaabra ( $pass+pass$), kadabraka ( $pass+pass+pass$), kadabraabra ( $pass+pass+pass$) and so on.

Input Format
First line contains an integer $T$, the total number of test cases. Then $T$ test cases follow.
First line of each test case contains $N$, the number of users with passwords. Second line contains N space separated strings, $pass pass \dots pass[N]$, representing the passwords of each user. Third line contains a string, loginAttempt, for which Yu has to tell whether it will be accepted or not.

Constraints $1 \le T \le 10$ $1 \le N \le 10$ $pass[i] \ne pass[j], 1 \le i \textless j \le N$ $1 \le length(pass[i]) \le 10, where\ i \in \left[1,N\right]$ $1 \le length(loginAttempt) \le 2000$
loginAttempt and $pass[i]$ contains only lowercase latin characters (‘a’-‘z’).

Output Format
For each valid string, Yu has to print the actual order of passwords, separated by space, whose concatenation results into loginAttempt. If there are multiple solutions, print any of them. If loginAttempt can’t be accepted by the password verification system, then print WRONG PASSWORD.

Sample Input 0

3
6
because can do must we what
wedowhatwemustbecausewecan
2
hello planet
helloworld
3
ab abcd cd
abcd


Sample Output 0

we do what we must because we can
ab cd


Explanation 0
Sample Case #00: wedowhatwemustbecausewecan is the concatenation of passwords {we, do, what, we, must, because, we, can}. That is

loginAttempt = pass + pass + pass + pass +  pass + pass + pass + pass


Note that any password can repeat any number of times.

Sample Case #01: We can’t create string helloworld using the strings {hello",planet}.

Sample Case #02: There are two ways to create loginAttempt (abcd). Both pass = "abcd" and pass + pass = "ab cd" are valid answers.

Sample Input 1

3
4
ozkxyhkcst xvglh hpdnb zfzahm
zfzahm
4
gurwgrb maqz holpkhqx aowypvopu
gurwgrb
10
a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa
aaaaaaaaaab


Sample Output 1

zfzahm
gurwgrb


Solution
We can solve this problem recursively and use memoization to avoid running out of time. The basic algorithm goes as follows:
– Iterate over all indices $i$ of loginAttempt:
– Split loginAttempt into two parts left = loginAttempt.substring(0,i) and right = loginAttempt.substring(i).
– Call isValid(left) and isValid(right).
– If both calls return true, then loginAttempt is valid.

Full code

public class PasswordCracker {
static Set cache; // memoization

private static boolean isValid(String loginAttempt, Set pass, List out) {
boolean ans = false;

return false;
}

return true;
} else {
}

for (int i = 0; i < loginAttempt.length(); i++) {
ans = isValid(left, pass, out) && isValid(right, pass, out);
if (ans) {
return true;
}
}

return ans;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);

int tests = in.nextInt();
for (int t = 1; t <= tests; t++) {
int n = in.nextInt();
Set pass = new HashSet();
for (int i = 0; i < n; i++) {
}

cache = new HashSet();
boolean res = isValid(loginAttempt, pass, out);
if (res) {
for (String p : out) {
System.out.print(p + " ");
}
} else {
`