中打印所有匹配模式的单词
原文:
给定一个单词字典，其中每个单词都遵循 camelcase 符号，打印字典中与给定的仅由大写字符组成的模式匹配的所有单词。 camelcase 是写复合词或短语的做法，这样每个单词或缩写都以大写字母开头。常见的例子包括:“powerpoint”和“wikipedia”、“geeksforgeeks”、“codeblocks”等。 例:
input:
dict[] = ["hi", "hello", "helloworld", "hitech", "higeek",
"hitechworld", "hitechcity", "hitechlab"]
for pattern "ht",
output: ["hitech", "hitechworld", "hitechcity", "hitechlab"]
for pattern "h",
output: ["hi", "hello", "helloworld", "hitech", "higeek",
"hitechworld", "hitechcity", "hitechlab"]
for pattern "htc",
output: ["hitechcity"]
input:
dict[] = ["welcomegeek","welcometogeeksforgeeks", "geeksforgeeks"]
for pattern "wtg",
output: ["welcometogeeksforgeeks"]
for pattern "gfg",
output: [geeksforgeeks]
for pattern "gg",
output: no match found
这个想法是将所有的字典键一个接一个地插入到 trie 中。此处的关键字仅指 camelcase 符号中原始单词的大写字符。如果我们第一次遇到密钥，我们需要将最后一个节点标记为叶节点，并将该密钥的完整单词插入到与叶节点相关联的向量中。如果我们遇到一个已经在 trie 中的关键字，我们用当前单词更新与叶节点相关的向量。处理完所有词典单词后，我们在 trie 中搜索模式，并打印所有与该模式匹配的单词。 以下是上述思路的实现–
c
// c program to print all words in the camelcase
// dictionary that matches with a given pattern
#include
using namespace std;
// alphabet size (# of upper-case characters)
#define alphabet_size 26
// a trie node
struct trienode
{
trienode* children[alphabet_size];
// isleaf is true if the node represents
// end of a word
bool isleaf;
// vector to store list of complete words
// in leaf node
list word;
};
// returns new trie node (initialized to nulls)
trienode* getnewtrienode(void)
{
trienode* pnode = new trienode;
if (pnode)
{
pnode->isleaf = false;
for (int i = 0; i < alphabet_size; i )
pnode->children[i] = null;
}
return pnode;
}
// function to insert word into the trie
void insert(trienode* root, string word)
{
int index;
trienode* pcrawl = root;
for (int level = 0; level < word.length(); level )
{
// consider only uppercase characters
if (islower(word[level]))
continue;
// get current character position
index = int(word[level]) - 'a';
if (!pcrawl->children[index])
pcrawl->children[index] = getnewtrienode();
pcrawl = pcrawl->children[index];
}
// mark last node as leaf
pcrawl->isleaf = true;
// push word into vector associated with leaf node
(pcrawl->word).push_back(word);
}
// function to print all children of trie node root
void printallwords(trienode* root)
{
// if current node is leaf
if (root->isleaf)
{
for(string str : root->word)
cout << str << endl;
}
// recurse for all children of root node
for (int i = 0; i < alphabet_size; i )
{
trienode* child = root->children[i];
if (child)
printallwords(child);
}
}
// search for pattern in trie and print all words
// matching that pattern
bool search(trienode* root, string pattern)
{
int index;
trienode* pcrawl = root;
for (int level = 0; level < pattern.length(); level )
{
index = int(pattern[level]) - 'a';
// invalid pattern
if (!pcrawl->children[index])
return false;
pcrawl = pcrawl->children[index];
}
// print all words matching that pattern
printallwords(pcrawl);
return true;
}
// main function to print all words in the camelcase
// dictionary that matches with a given pattern
void findallwords(vector dict, string pattern)
{
// construct trie root node
trienode* root = getnewtrienode();
// construct trie from given dict
for (string word : dict)
insert(root, word);
// search for pattern in trie
if (!search(root, pattern))
cout << "no match found";
}
// driver function
int main()
{
// dictionary of words where each word follows
// camelcase notation
vector dict = {
"hi", "hello", "helloworld", "hitech", "higeek",
"hitechworld", "hitechcity", "hitechlab"
};
// pattern consisting of uppercase characters only
string pattern = "ht";
findallwords(dict, pattern);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all words in the camelcase
// dictionary that matches with a given pattern
import java.util.arraylist;
import java.util.arrays;
import java.util.list;
public class camelcase {
// alphabet size (# of upper-case characters)
static final int alphabet_size = 26;
// a trie node
static class trienode {
trienode[] children = new trienode[alphabet_size];
// isleaf is true if the node represents
// end of a word
boolean isleaf;
// vector to store list of complete words
// in leaf node
list word;
public trienode() {
isleaf = false;
for (int i = 0; i < alphabet_size; i )
children[i] = null;
word = new arraylist();
}
}
static trienode root;
// function to insert word into the trie
static void insert(string word) {
int index;
trienode pcrawl = root;
for (int level = 0; level < word.length(); level ) {
// consider only uppercase characters
if (character.islowercase(word.charat(level)))
continue;
// get current character position
index = word.charat(level) - 'a';
if (pcrawl.children[index] == null)
pcrawl.children[index] = new trienode();
pcrawl = pcrawl.children[index];
}
// mark last node as leaf
pcrawl.isleaf = true;
// push word into vector associated with leaf node
(pcrawl.word).add(word);
}
// function to print all children of trie node root
static void printallwords(trienode root) {
// if current node is leaf
if (root.isleaf) {
for (string str : root.word)
system.out.println(str);
}
// recurse for all children of root node
for (int i = 0; i < alphabet_size; i ) {
trienode child = root.children[i];
if (child != null)
printallwords(child);
}
}
// search for pattern in trie and print all words
// matching that pattern
static boolean search(string pattern) {
int index;
trienode pcrawl = root;
for (int level = 0; level < pattern.length(); level ) {
index = pattern.charat(level) - 'a';
// invalid pattern
if (pcrawl.children[index] == null)
return false;
pcrawl = pcrawl.children[index];
}
// print all words matching that pattern
printallwords(pcrawl);
return true;
}
// main function to print all words in the camelcase
// dictionary that matches with a given pattern
static void findallwords(list dict, string pattern)
{
// construct trie root node
root = new trienode();
// construct trie from given dict
for (string word : dict)
insert(word);
// search for pattern in trie
if (!search(pattern))
system.out.println("no match found");
}
// driver function
public static void main(string args[]) {
// dictionary of words where each word follows
// camelcase notation
list dict = arrays.aslist("hi", "hello",
"helloworld", "hitech", "higeek",
"hitechworld", "hitechcity",
"hitechlab");
// pattern consisting of uppercase characters only
string pattern = "ht";
findallwords(dict, pattern);
}
}
// this code is contributed by sumit ghosh
c
// c# program to print all words in
// the camelcase dictionary that
// matches with a given pattern
using system;
using system.collections.generic;
class gfg
{
// alphabet size (# of upper-case characters)
static int alphabet_size = 26;
// a trie node
public class trienode
{
public trienode[] children = new
trienode[alphabet_size];
// isleaf is true if the node represents
// end of a word
public bool isleaf;
// vector to store list of complete words
// in leaf node
public list word;
public trienode()
{
isleaf = false;
for (int i = 0; i < alphabet_size; i )
children[i] = null;
word = new list();
}
}
static trienode root;
// function to insert word into the trie
static void insert(string word)
{
int index;
trienode pcrawl = root;
for (int level = 0;
level < word.length; level )
{
// consider only uppercase characters
if (char.islower(word[level]))
continue;
// get current character position
index = word[level] - 'a';
if (pcrawl.children[index] == null)
pcrawl.children[index] = new trienode();
pcrawl = pcrawl.children[index];
}
// mark last node as leaf
pcrawl.isleaf = true;
// push word into vector
// associated with leaf node
(pcrawl.word).add(word);
}
// function to print all children
// of trie node root
static void printallwords(trienode root)
{
// if current node is leaf
if (root.isleaf)
{
foreach (string str in root.word)
console.writeline(str);
}
// recurse for all children of root node
for (int i = 0; i < alphabet_size; i )
{
trienode child = root.children[i];
if (child != null)
printallwords(child);
}
}
// search for pattern in trie and
// print all words matching that pattern
static bool search(string pattern)
{
int index;
trienode pcrawl = root;
for (int level = 0;
level < pattern.length;
level )
{
index = pattern[level] - 'a';
// invalid pattern
if (pcrawl.children[index] == null)
return false;
pcrawl = pcrawl.children[index];
}
// print all words matching that pattern
printallwords(pcrawl);
return true;
}
// main function to print all words
// in the camelcase dictionary that
// matches with a given pattern
static void findallwords(list dict,
string pattern)
{
// construct trie root node
root = new trienode();
// construct trie from given dict
foreach (string word in dict)
insert(word);
// search for pattern in trie
if (!search(pattern))
console.writeline("no match found");
}
// driver code
public static void main(string []args)
{
// dictionary of words where each word follows
// camelcase notation
list dict = new list{"hi", "hello",
"helloworld", "hitech",
"higeek", "hitechworld",
"hitechcity", "hitechlab"};
// pattern consisting of
// uppercase characters only
string pattern = "ht";
findallwords(dict, pattern);
}
}
// this code is contributed by princi singh
输出:
hitech
hitechcity
hitechlab
hitechworld
本文由阿迪蒂亚·戈尔供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
