FORM STRING

CONCEPTS USED:

Dynamic programming

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT$($SIMPLIFIED$)$:

Arnab is now given a String S. He is given N different typed of pieces of sticks with strings written on them(we have an infinite supply of each type). Now Arnab is asked whether he can form the string S using the sticks by placing them one after another. If yes print "Yes" else print "No" (without double quotes).

For Example :

1
prepBytes
5
pre
ab
pBy
cd
tes

we can form prepBytes using the strings pre+pBy+tes.  

OBSERVATION:

Iterate over all the strings, checking if the target string "begins" with any of them.

Take the longest string with which the target string begins, remove it from the list and trim it from the main string.

Rinse, repeat.

Stop when you’re left with a 0 length target string.

You are encouraged to read the above observation carefully and try to attempt the problem on your own ,before looking at the solution.

See original problem statement here

SOLVING APPROACH:

BRUTE FORCE:

Do it like you would a password generator i.e. word1+word1+word1 > word1+word1+word2 > word1+word1+word3 etc etc etc

The trick there is the length so youd have to try all combinations of 2 or more words and you don’t know where to set the limit. Very time consuming.

DYNAMIC PROGRAMMING:

Look at this function:

>function Possible(array A, string s)
>If s is empty, return true.
>compute the array P of all strings in A that are a prefix of s.
>If P is empty, return false.
>for each string p in P:
>if Possible(A with p removed, s with prefix p removed) return true
>return false

Use a map to mark all the substrings encountered.If you end up with an empty string, print "Yes" else print "No".

Refer to code for better understanding and make use of programming courses for students online.

SOLUTIONS:

 #include <bits/stdc++.h>
     using namespace std;
     map<string,int> mp;
      bool solve(string s)
     {

      if(mp[s])
      {
      if(mp[s]==1)
      return true;
      }
      string w="";
      int fl=2;
      for(int i=0;i<s.length();i++)
      {
      w+=s[i];
      if(mp[w]==1&&solve(s.substr(i+1)))
     {
      mp[s]=1;
      return true;
     }
     }
     mp[s]=2;
     return false;
      }  
     int main()
     {  

      int t;
      cin>>t;
      while(t--)
     {
      mp.clear();
      string s;
      cin>>s;
      int n;
      cin>>n;
      string st;
     for(int i=0;i<n;i++)
     {
     cin>>st;
     mp[st]=1;
     }
     cout<<(solve(s)?"Yes":"No")<<endl;
    } 
     return 0;
     }
 import java.util.Scanner;
     import java.util.*;

    class HelloWorld{

    Map<String,Integer> mp=new HashMap<String,Integer>();

    boolean solve(String s){
        if(mp.get(s) != null){
            if(mp.get(s) == 1)
                return true;
        }
        String w = "";
        int fl=2;
        for(int i=0;i<s.length();i++){
            w+=s.charAt(i);
            if(mp.get(w) != null){
                if(mp.get(w)==1 && solve(s.substring(i+1))){
                    mp.put(s,1);
                    return true;
                }
            }
        }
        mp.put(s,2);
        return false;
    }
    public static void main(String []args){
        Scanner myObj = new Scanner(System.in);
        int t=Integer.parseInt(myObj.nextLine());
        HelloWorld  h = new HelloWorld();
        while(t-- > 0){
            h.mp.clear();
            String s=myObj.nextLine();
            int n=Integer.parseInt(myObj.nextLine());
            String st;
            for(int i=0;i<n;i++){
                st=myObj.nextLine();
                h.mp.put(st,1);
            }
            boolean res = h.solve(s);
            System.out.println(res?"Yes":"No");
        }
    }
     }


It uses O(n) space for memoization.

Previous post RAHUL AND PUZZLE WORLD
Next post CHEATING CLASS

Leave a Reply

Your email address will not be published. Required fields are marked *