#PROBLEM LINK:
Author: Chandan Boruah
Tester: Jaideep Pyne
Editorialist: Chandan Boruah
#DIFFICULTY:
Medium
#PREREQUISITES:
DP/Graph theory
#PROBLEM:
Given a few words, find if another given word, a superword, can be formed by concatenation of the given words.
#QUICK EXPLANATION:
Use a queue to enter the superword and keep taking substrings of it such that the words that are part of it are removed from beginning till the word becomes null.
#EXPLANATION:
Use a queue, enter the given word to be formed (superword) in the queue. Take substring of the word by removing from beginning all words that it starts with in the given list of words. Keep dequeuing like this, till the word becomes empty. If it happens it can be done, else no it cant.
#AUTHOR’S SOLUTIONS:
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
string[]s=Console.ReadLine().Split();
int n=int.Parse(s[0]);
int m=int.Parse(s[1]);
string[]arr=Console.ReadLine().Split();
for(int ii=0;ii<m;ii++)
{
string nn=Console.ReadLine();
Queueqq=new Queue();
Listdone=new List();
qq.Enqueue(nn);
done.Add(nn);
bool b=false;
while(qq.Count>0)
{
string now=qq.Dequeue();
for(int i=0;i<arr.Length;i++)
{
if(now==arr[i]){b=true;break;}
if(now.StartsWith(arr[i]))
{
if(!done.Contains(now.Substring(arr[i].Length)))
{
done.Add(now.Substring(arr[i].Length));
qq.Enqueue(now.Substring(arr[i].Length));
}
}
}if(b)break;
}
if(b)Console.WriteLine(“Yes”);
else Console.WriteLine(“No”);
}
}
}
#RELATED PROBLEMS: