HackerRank Password Cracker problem solution

In this HackerRank Password Cracker problem solution, There are n users registered on the website CuteKittens.com. Each of them has a unique password represented by pass[1], pass[2], ..., pass[N]. As this is a very lovely site, many people want to access those awesomely cute pics of the kittens. But the adamant admin does not want the site to be available to the general public, so only those people who have passwords can access it.

Yu, being an awesome hacker finds a loophole in the password verification system. A string which is a 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. Given access to each of the N passwords, and also have a string loginAttempt, determine whether this string be accepted by the password verification system of the website. If all of the loginAttempt strings can be created by concatenating password strings, it is accepted. In this case, return the passwords in the order they must be concatenated, each separated by a single space on one line. If the password attempt will not be accepted, return 'WRONG PASSWORD.

Problem solution in Python.

import sys
sys.setrecursionlimit(5000)
testcases = int(input())
memo = {}

def solve(attempt, passwords, output, strLoc):
    global memo
    if strLoc not in memo and strLoc != len(attempt):
        fail_path = True
        for password in passwords:
            if len(password) <= (len(attempt) - strLoc):
                if password == (attempt[strLoc:(strLoc+len(password))]):
                    output.append(password)
                    output = solve(attempt, passwords, output, strLoc + len(password))
                    if len("".join(output)) == len(attempt):
                        fail_path = False
                        break
        if fail_path:
            memo[strLoc] = True

    if strLoc in memo:
        output = output[:-1]

    return output

        
for i in range(testcases):
    memo = {}
    input()
    passwords = input().split(" ")
    attempt = input()
    output = solve(attempt, passwords, [], 0)
    if len("".join(output)) != len(attempt):
        print("WRONG PASSWORD")
    else:
        print(" ".join(output))
    

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
    private static Stack<String> passwords;
    private static Set<String> badLoginAttempt;

    private static boolean calc(String[] pass, String loginAttempt) {
        if(badLoginAttempt.contains(loginAttempt)) {
            return false;
        }
        if(loginAttempt.length() == 0) {
            return true;
        }
        for(String p : pass) {
            if(loginAttempt.startsWith(p) && calc(pass, loginAttempt.substring(p.length()))) {
                passwords.push(p);
                return true;
            }
        }
        badLoginAttempt.add(loginAttempt);
        return false;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();
            String[] pass = new String[n];
            for(int j = 0; j < n; j++) {
                pass[j] = in.next();
            }
            String loginnAttempt = in.next();
            passwords = new Stack<>();
            badLoginAttempt = new HashSet<>();
            boolean result = calc(pass, loginnAttempt);
            if(result) {
                while (!passwords.isEmpty()) {
                    System.out.print(passwords.pop() + " ");
                }
                System.out.println();
            } else {
                System.out.println("WRONG PASSWORD");
            }
        }
    }
}

Problem solution in C++.

#include <iostream>
#include<string>
#include <stdlib.h>
#include <map>

using namespace std;
int sizes=0;
int check=0;
map<int , int> maper;
void preform(string arrays[],int n,string attemt,int start,string outer[]){
    if(maper[start]==2){
        return;
    }
    if(check==1){
        return;

    }
    if(start==attemt.length()){
        check=1;
        return;
         }
    for(int i = 0;i<n;i++){
            string x = arrays[i];
        if(x.length()>attemt.length()-start){
            continue;
        }
        string newstr = attemt.substr(start,x.length());
        int newsizes = sizes;
        if(x.compare(newstr)==0){
            outer[sizes]=newstr;
            sizes++;
            preform(arrays,n,attemt,start+x.length(),outer);
        }
        if(check==1){
            return;
        }
       sizes=newsizes;

    }
    if(check==0){
        maper[start]=2;
    }

}

int main()
{
    int t;
    cin>>t;
    string out[t];
    for (int i = 0;i<t;i++){
        string outer[2001];
        int n;
        cin>>n;
        string arrays[n];
        for(int j=0;j<n;j++){
            cin>>arrays[j];
        }
        string attempt;
        cin>>attempt;
        preform(arrays,n,attempt,0,outer);
        if(check==1){
            for(int j = 0;j<sizes;j++){
            out[i]+=outer[j]+" ";
              }
            sizes=0;
            check=0;
            maper.clear();
        }else{
            out[i]="WRONG PASSWORD";
            sizes=0;
            check=0;
            maper.clear();
        }
    }
    for(int i = 0;i<t;i++){
        cout<<out[i]<<'\n';
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(int idx);
char a[10][11],str[2001];
int dp[2000],N,len;

int main(){
  int T,i;
  scanf("%d",&T);
  while(T--){
    memset(dp,-1,sizeof(dp));
    scanf("%d",&N);
    for(i=0;i<N;i++)
      scanf("%s",&a[i][0]);
    scanf("%s",str);
    len=strlen(str);
    solve(0);
    if(dp[0]==-2)
      printf("WRONG PASSWORD\n");
    else{
      i=0;
      while(i<len){
        printf("%s ",&a[dp[i]][0]);
        i+=strlen(&a[dp[i]][0]);
      }
      printf("\n");
    }
  }
  return 0;
}
void solve(int idx){
  int i;
  if(idx>=len || dp[idx]!=-1)
    return;
  for(i=0;i<N;i++)
    if(!strncmp(&str[idx],&a[i][0],strlen(&a[i][0])))
      if(!str[idx+strlen(&a[i][0])]){
        dp[idx]=i;
        break;
      }
      else{
        solve(idx+strlen(&a[i][0]));
        if(dp[idx+strlen(&a[i][0])]>=0){
          dp[idx]=i;
          break;
        }
      }
  if(dp[idx]==-1)
    dp[idx]=-2;
  return;
}