Password Cracker


Problem Statement :


There are n users registered on a website CuteKittens.com. Each of them has a unique password represented by pass[1], pass[2], ..., pass[N]. As this 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  or more times in that string. Given access to each of the  passwords, and also have a string , determine whether this string be accepted by the password verification system of the website. If all of the  string 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 PWASSWORD'.


Concatenate the passwords in index order  to match 'abba',  to match 'baab',  to match 'abab' or  to match $baba'. No combination of 1 or more passwords can be concatenated to match 'aba'. Return 'WRONG PASSWORD'.

Function Description

Complete the passwordCracker function in the editor below.

passwordCracker has the following parameters:
- string passwords[n]: a list of password strings
- string loginAttempt: the string to attempt to create

Returns
- string: Return the passwords as a single string in the order required for the password to be accepted, each separated by a space. If it is not possible to form the string, return the string WRONG PASSWORD.

Input Format

The first line contains an integer t, the total number of test cases.

Each of the next  sets of three lines is as follows:
- The first line of each test case contains n, the number of users with passwords.
- The second line contains n space-separated strings, passwords[i], that represent the passwords of each user.
- The third line contains a string, loginAttempt, which Yu must test for acceptance.


Solution :



title-img 


                            Solution in C :

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;
}
                        


                        Solution in C++ :

In  C++  :







#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

#include <unordered_set>

using namespace std;


void putReverses(vector< string > &words, unordered_set< string > &wordSet)
{
    int n = words.size();
    for(int i = 0;i != n;i++)
    {
        reverse(words[i].begin(), words[i].end());
        wordSet.insert(words[i]);
    }
}

vector< string > findComb(const string &str, vector< string > &words)
{
    vector< string > result;
    int m = str.size();
    
    unordered_set< string > wordSet;
    putReverses(words, wordSet);
    
    vector< char > valid(m + 1, 0);
    valid[0] = 1;
    vector< int > validLens(m + 1);
    
    for(int len = 1;len <= m;len++)
    {
        int i = len - 1;
        string word;
        for(int j = i;j >= 0;j--)
        {
            word += str[j];
            if(valid[j] && wordSet.find(word) != wordSet.end())
            {
                valid[len] = 1;
                validLens[len] = len - j;
                break;
            }
        }
    }
    
    if(valid[m] == 0) { return result; }
    
    int len = m;
    while(len)
    {
        result.push_back(str.substr(len - validLens[len], validLens[len]));
        len -= validLens[len];
    }
    
    reverse(result.begin(), result.end());
    return result;
}


int main()
{
    int T, N;
    string word, str;
    cin >> T;
    while(T--)
    {
        cin >> N;
        vector< string > words;
        while(N--)
        {
            cin >> word;
            words.push_back(word);
        }
        
        cin >> str;
        
        vector< string > comb(findComb(str, words));
        if(comb.empty()) { cout << "WRONG PASSWORD"; }
        else
        {
            int m = comb.size();
            cout << comb[0];
            for(int i = 1;i != m;i++)
            {
                cout << " " << comb[i];
            }
        }
        
        cout << endl;
    }
    
    return 0;
}
                    


                        Solution in Java :

In  Java :






import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i = 0; i < N; i++){
            int cnt = sc.nextInt();
            Set<String> dict = new HashSet<String>();
            Map<String,Boolean> map = new HashMap<String,Boolean>();
            for(int j = 0; j < cnt; j++){
                dict.add(sc.next());
            }
            String s = sc.next();
            boolean res = dfs(s,dict,"",map);
            if (!res){
                System.out.println("WRONG PASSWORD");
            }
        }
    }
    
    private static boolean dfs(String s, Set<String> dict, String path,Map<String,Boolean> map){
        
        if (s == null || s.length() == 0){
            System.out.println(path.trim());
            return true;
        }
        if (map.containsKey(s)){
            return map.get(s);
        }
        for(String word : dict){
            if (!s.startsWith(word)) continue;
            if (dfs(s.substring(word.length()),dict,path + word + " ",map)){
                map.put(s,true);
                return true;
            }
        }
        map.put(s,false);
        return false;
    }
}
                    


                        Solution in Python : 
                            
In  Python3 :








t = int(input().strip())

def solve(ws, x):
    dead_end = set()
    
    stack = []
    stack.append(([], x))
    while stack:
        acc, cur = stack.pop()
        
        if cur == "":
            return acc

        is_dead_end = True
        for w in ws:
            if cur.startswith(w):
                cur2 = cur[len(w):]
                if cur2 in dead_end:
                    continue
                is_dead_end = False    
                acc2 = acc[:]
                acc2.append(w)
                stack.append((acc2, cur2))
        
        if is_dead_end:
            dead_end.add(cur)
            
for ti in range(t):
    n = int(input().strip())
    ws = [tmp for tmp in input().strip().split(' ')]
    x = input().strip()
    answer = solve(ws, x)
    if answer is None:
        print("WRONG PASSWORD")
    else:
        print(" ".join(answer))


View More Similar Problems

Balanced Brackets

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ]. Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and (). A matching pair of brackets is not balanced if the set of bra

View Solution →

Equal Stacks

ou have three stacks of cylinders where each cylinder has the same diameter, but they may vary in height. You can change the height of a stack by removing and discarding its topmost cylinder any number of times. Find the maximum possible height of the stacks such that all of the stacks are exactly the same height. This means you must remove zero or more cylinders from the top of zero or more of

View Solution →

Game of Two Stacks

Alexa has two stacks of non-negative integers, stack A = [a0, a1, . . . , an-1 ] and stack B = [b0, b1, . . . , b m-1] where index 0 denotes the top of the stack. Alexa challenges Nick to play the following game: In each move, Nick can remove one integer from the top of either stack A or stack B. Nick keeps a running sum of the integers he removes from the two stacks. Nick is disqualified f

View Solution →

Largest Rectangle

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed. There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by . If you join adjacent buildings, they will form a solid rectangle

View Solution →

Simple Text Editor

In this challenge, you must implement a simple text editor. Initially, your editor contains an empty string, S. You must perform Q operations of the following 4 types: 1. append(W) - Append W string to the end of S. 2 . delete( k ) - Delete the last k characters of S. 3 .print( k ) - Print the kth character of S. 4 . undo( ) - Undo the last (not previously undone) operation of type 1 or 2,

View Solution →

Poisonous Plants

There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plan

View Solution →