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

No Prefix Set

There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio

View Solution →

Cube Summation

You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor

View Solution →

Direct Connections

Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do

View Solution →

Subsequence Weighting

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =

View Solution →

Kindergarten Adventures

Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti

View Solution →

Mr. X and His Shots

A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M

View Solution →