# Word formation using concatenation of two dictionary words

Given a dictionary find out if given word can be made by two words in the dictionary.

Note: Words in the dictionary must be unique and the word to be formed should not be a repetition of same words that are present in the Trie.

Examples:

Input : dictionary[] = {"news", "abcd", "tree",
"geeks", "paper"}
word = "newspaper"
Output : Yes
We can form "newspaper" using "news" and "paper"

Input : dictionary[] = {"geeks", "code", "xyz",
"forgeeks", "paper"}
word = "geeksforgeeks"
Output : Yes

Input : dictionary[] = {"geek", "code", "xyz",
"forgeeks", "paper"}
word = "geeksforgeeks"
Output : No

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is store all words of dictionary in a Trie. We do prefix search for given word. Once we find a prefix, we search for rest of the word.

Algorithm :

1- Store all the words of the dictionary in a Trie.
2- Start searching for the given word in Trie.
If it partially matched then split it into two
parts and then search for the second part in
the Trie.
3- If both found, then return true.
4- Otherwise return false.

Below is the implementation of above idea.

## C++

 // C++ program to check if a string can be // formed by concatenating two words #include using namespace std;    // Converts key current character into index // use only 'a' through 'z' #define char_int(c) ((int)c - (int)'a')    // Alphabet size #define SIZE (26)    // Trie Node struct TrieNode {     TrieNode *children[SIZE];        // isLeaf is true if the node represents     // end of a word     bool isLeaf; };    // Returns new trie node (initialized to NULLs) TrieNode *getNode() {     TrieNode * newNode = new TrieNode;     newNode->isLeaf = false;     for (int i =0 ; i< SIZE ; i++)         newNode->children[i] = NULL;     return newNode; }    // If not present, inserts key into Trie // If the key is prefix of trie node, just // mark leaf node void insert(TrieNode *root, string Key) {     int n = Key.length();     TrieNode * pCrawl = root;        for (int i=0; ichildren[index] == NULL)             pCrawl->children[index] = getNode();            pCrawl = pCrawl->children[index];     }        // make last node as leaf node     pCrawl->isLeaf = true; }    // Searches a prefix of key. If prefix is present, // returns its ending position in string. Else // returns -1. int findPrefix(struct TrieNode *root, string key) {     int pos = -1, level;     struct TrieNode *pCrawl = root;        for (level = 0; level < key.length(); level++)     {         int index = char_int(key[level]);         if (pCrawl->isLeaf == true)             pos = level;         if (!pCrawl->children[index])             return pos;            pCrawl = pCrawl->children[index];     }     if (pCrawl != NULL && pCrawl->isLeaf)         return level; }    // Function to check if word formation is possible // or not bool isPossible(struct TrieNode* root, string word) {     // Search for the word in the trie and     // store its position upto which it is matched     int len = findPrefix(root, word);        // print not possible if len = -1 i.e. not     // matched in trie     if (len == -1)         return false;        // If word is partially matched in the dictionary     // as another word     // search for the word made after splitting     // the given word up to the length it is     // already,matched     string split_word(word, len, word.length()-(len));     int split_len = findPrefix(root, split_word);        // check if word formation is possible or not     return (len + split_len == word.length()); }    // Driver program to test above function int main() {     // Let the given dictionary be following     vector dictionary = {"geeks", "forgeeks",                                     "quiz", "geek"};        string word = "geeksquiz"; //word to be formed        // root Node of trie     TrieNode *root = getNode();        // insert all words of dictionary into trie     for (int i=0; i

## Java

 import java.util.ArrayList; import java.util.List;    // Java program to check if a string can be  // formed by concatenating two words  public class GFG {                 // Alphabet size      final static int SIZE = 26;             // Trie Node      static class TrieNode      {          TrieNode[] children = new TrieNode[SIZE];                 // isLeaf is true if the node represents          // end of a word          boolean isLeaf;                     // constructor          public TrieNode() {              isLeaf = false;              for (int i =0 ; i< SIZE ; i++)                      children[i] = null;          }      }                    static TrieNode root;             // If not present, inserts key into Trie      // If the key is prefix of trie node, just      // mark leaf node      static void insert(TrieNode root, String Key)      {          int n = Key.length();          TrieNode pCrawl = root;                 for (int i=0; i findPrefix(TrieNode root, String key)      {          List prefixPositions = new ArrayList();         int level;          TrieNode pCrawl = root;                 for (level = 0; level < key.length(); level++)          {              int index = key.charAt(level) - 'a';              if (pCrawl.isLeaf == true)                  prefixPositions.add(level);              if (pCrawl.children[index] == null)                  return prefixPositions;                     pCrawl = pCrawl.children[index];          }          if (pCrawl != null && pCrawl.isLeaf)              prefixPositions.add(level);                      return prefixPositions;       }             // Function to check if word formation is possible      // or not      static boolean isPossible(TrieNode root, String word)      {          // Search for the word in the trie and get its prefix positions         // upto which there is matched          List prefixPositions1 = findPrefix(root, word);                 // Word formation is not possible if the word did not have          // at least one prefix match         if (prefixPositions1.isEmpty())              return false;                 // Search for rest of substring for each prefix match         for (Integer len1 : prefixPositions1) {             String restOfSubstring = word.substring(len1, word.length());              List prefixPositions2 = findPrefix(root, restOfSubstring);             for (Integer len2 : prefixPositions2) {                 // check if word formation is possible                 if (len1 + len2 == word.length())                     return true;             }         }                    return false;     }             // Driver program to test above function      public static void main(String args[])      {          // Let the given dictionary be following          String[] dictionary = {"news", "newspa", "paper", "geek"};                 String word = "newspaper"; //word to be formed                 // root Node of trie          root = new TrieNode();                 // insert all words of dictionary into trie          for (int i=0; i

## C#

 // C# program to check if a string can be  // formed by concatenating two words  using System; using System.Collections.Generic;    class GFG  {                 // Alphabet size      readonly public static int SIZE = 26;             // Trie Node      public class TrieNode      {          public TrieNode []children = new TrieNode[SIZE];                 // isLeaf is true if the node          // represents end of a word          public bool isLeaf;                     // constructor          public TrieNode()          {              isLeaf = false;              for (int i = 0 ; i < SIZE ; i++)                      children[i] = null;          }      }      static TrieNode root;             // If not present, inserts key into Trie      // If the key is prefix of trie node, just      // mark leaf node      static void insert(TrieNode root, String Key)      {          int n = Key.Length;          TrieNode pCrawl = root;                 for (int i = 0; i < n; i++)          {              int index = Key[i] - 'a';                     if (pCrawl.children[index] == null)                  pCrawl.children[index] = new TrieNode();                     pCrawl = pCrawl.children[index];          }                 // make last node as leaf node          pCrawl.isLeaf = true;      }             // Searches a prefix of key. If prefix      // is present, returns its ending position      //  in string. Else returns -1.      static List findPrefix(TrieNode root, String key)      {          List prefixPositions = new List();          int level;          TrieNode pCrawl = root;                 for (level = 0; level < key.Length; level++)          {              int index = key[level] - 'a';              if (pCrawl.isLeaf == true)                  prefixPositions.Add(level);              if (pCrawl.children[index] == null)                  return prefixPositions;                     pCrawl = pCrawl.children[index];          }          if (pCrawl != null && pCrawl.isLeaf)              prefixPositions.Add(level);                     return prefixPositions;      }             // Function to check if word       // formation is possible or not      static bool isPossible(TrieNode root, String word)      {          // Search for the word in the trie          // and get its prefix positions          // upto which there is matched          List prefixPositions1 = findPrefix(root, word);                 // Word formation is not possible          // if the word did not have          // at least one prefix match          if (prefixPositions1.Count==0)              return false;                 // Search for rest of substring          // for each prefix match          foreach (int len1 in prefixPositions1)          {              String restOfSubstring = word.Substring(len1,                                         word.Length-len1);              List prefixPositions2 = findPrefix(root,                                         restOfSubstring);              foreach (int len2 in prefixPositions2)              {                                     // check if word formation is possible                  if (len1 + len2 == word.Length)                      return true;              }          }          return false;      }             // Driver code      public static void Main(String []args)      {          // Let the given dictionary be following          String[] dictionary = {"news", "newspa", "paper", "geek"};                 // word to be formed          String word = "newspaper";                 // root Node of trie          root = new TrieNode();                 // insert all words of dictionary into trie          for (int i = 0; i < dictionary.Length; i++)              insert(root, dictionary[i]);                 if(isPossible(root, word))              Console.WriteLine( "Yes");          else             Console.WriteLine("No");      }  }     // This code is contributed by 29AjayKumar

Output:

Yes

Exercise :
A generalized version of the problem is to check if a given word can be formed using concatenation of 1 or more dictionary words. Write code for the generalized version.