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
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<bits/stdc++.h> 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; i<n; i++) { int index = char_int(Key[i]); if (pCrawl->children[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<string> 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<dictionary.size(); i++) insert(root, dictionary[i]); isPossible(root, word) ? cout << "Yes": cout << "No"; return 0; } |
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<n; i++) { int index = Key.charAt(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<Integer> findPrefix(TrieNode root, String key) { List<Integer> prefixPositions = new ArrayList<Integer>(); 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<Integer> 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<Integer> 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<dictionary.length; i++) insert(root, dictionary[i]); if(isPossible(root, word)) System.out.println( "Yes"); else System.out.println("No"); } } // This code is contributed by Sumit Ghosh // Updated by Narendra Jha |
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<int> findPrefix(TrieNode root, String key) { List<int> prefixPositions = new List<int>(); 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<int> 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<int> 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.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments