FORM STRING

Last Updated on March 28, 2022 by Ria Pathak

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.

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

primes = [0] * 100006

def setPrimes():

	global primes

	for i in range(2, 100006):
		primes[i] = 1

	primes[0] = 0
	primes[1] = 0

	for i in range(2, 100006):

		for j in range(2 * i, 100006, i):
			primes[j] = 0

setPrimes()
for _ in range(int(input())):

	n = int(input())
	sum = 0
	i = 2

	while(n!=0):
		if( primes[i] == 1 ):
			k = i
			odd = 0
			while(k):
				if(primes[k % 10] == 1 and k % 10 != 2):
					odd = 1
					break
				
				k//=10
			
			if(odd == 0):
				sum += i
				n -= 1

		i += 1

	print(sum)

[forminator_quiz id="2182"]

This article tried to discuss Dynamic programming. Hope this blog helps you understand and solve the problem. To practice more problems on Dynamic programming you can check out MYCODE | Competitive Programming.