给定一本字典找出给定的单词是否可以由字典中的两个单词组成。 注：词典中的单词必须是唯一的，且要形成的单词不应重复出现在词典中的相同单词。
null
例如：
Input : dictionary[] = {"news", "abcd", "tree", "geeks", "paper"} word = "newspaper"Output : YesWe can form "newspaper" using "news" and "paper"Input : dictionary[] = {"geeks", "code", "xyz", "forgeeks", "paper"} word = "geeksforgeeks"Output : YesInput : dictionary[] = {"geek", "code", "xyz", "forgeeks", "paper"} word = "geeksforgeeks"Output : No
其想法是将字典中的所有单词存储在 崔 .我们对给定的单词进行前缀搜索。一旦我们找到前缀，我们就会搜索单词的其余部分。
算法：
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.
下面是上述想法的实现。
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 |
Javascript
<script> // Javascript program to check if a string // can be formed by concatenating two words // Alphabet size let SIZE = 26; // Trie Node class TrieNode { constructor() { this .isLeaf = false ; this .children = new Array(SIZE); for (let i = 0 ; i < SIZE; i++) this .children[i] = null ; } } let root; // If not present, inserts key into Trie // If the key is prefix of trie node, just // mark leaf node function insert(root, Key) { let n = Key.length; let pCrawl = root; for (let i = 0; i < n; i++) { let index = Key[i].charCodeAt(0) - 'a' .charCodeAt(0); 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. function findPrefix(root, key) { let prefixPositions = []; let level; let pCrawl = root; for (level = 0; level < key.length; level++) { let index = key[level].charCodeAt(0) - 'a' .charCodeAt(0); if (pCrawl.isLeaf == true ) prefixPositions.push(level); if (pCrawl.children[index] == null ) return prefixPositions; pCrawl = pCrawl.children[index]; } if (pCrawl != null && pCrawl.isLeaf) prefixPositions.push(level); return prefixPositions; } // Function to check if word formation // is possible or not function isPossible(root, word) { // Search for the word in the trie and // get its prefix positions upto which // there is matched let prefixPositions1 = findPrefix(root, word); // Word formation is not possible if // the word did not have at least one // prefix match if (prefixPositions1.length == 0) return false ; // Search for rest of substring for // each prefix match for (let len1 = 0; len1 < prefixPositions1.length; len1++) { let restOfSubstring = word.substring( prefixPositions1[len1], word.length); let prefixPositions2 = findPrefix( root, restOfSubstring); for (let len2 = 0; len2 < prefixPositions2.length; len2++) { // Check if word formation is possible if (prefixPositions1[len1] + prefixPositions2[len2] == word.length) return true ; } } return false ; } // Driver code let dictionary = [ "news" , "newspa" , "paper" , "geek" ]; // word to be formed let word = "newspaper" ; // Root Node of trie root = new TrieNode(); // Insert all words of dictionary into trie for (let i = 0; i < dictionary.length; i++) insert(root, dictionary[i]); if (isPossible(root, word)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by rag2127 </script> |
输出：
Yes
练习： 这个问题的一个广义版本是检查一个给定的单词是否可以使用一个或多个字典单词的串联来形成。为通用版本编写代码。
本文由 萨希尔·查布拉（阿克库） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
