算法设计：如何实现CamelCase模式匹配？代码示例

2021年3月28日15:58:45 发表评论 960 次浏览

本文概述

给定一个单词列表, 每个单词都遵循CamelCase表示法, 任务是打印词典中所有与给定模式匹配的所有单词, 这些模式仅由大写字符组成。

例子

输入：arr [] = [" WelcomeGeek", " WelcomeTolsbin", " lsbin"], 模式=" WTG"
输出：WelcomeTolsbin
说明：给定模式只有一个缩写, 即WelcomeTolsbin。
输入：arr [] = [" Hi", " Hello", " HelloWorld", " HiTech", " HiGeek", " HiTechWorld", " HiTechCity", " HiTechLab"], pattern =" HA"
输出：未找到匹配项
说明：给定的模式没有这样的缩写。

方法：

1. 遍历每个单词，并用给定字符串中找到的每个大写字母对该单词进行哈希。

例如：

For string = "lsbin"
then the hashing after every uppercase letter found is:
map {
     {G, lsbin}, {GF, lsbin}, {GFG, lsbin}
}

2. 在为列表中的所有字符串创建散列之后。在映射中搜索给定的模式，并打印映射到该模式的所有字符串。

下面是上述方法的实现：

C ++

// C++ to find CamelCase Pattern
// matching
#include "bits/stdc++.h"
using namespace std;
  
// Function that prints the camel
// case pattern matching
void CamelCase(vector<string>& words, string pattern)
{
  
     // Map to store the hashing
     // of each words with every
     // uppercase letter found
     map<string, vector<string> > map;
  
     // Traverse the words array
     // that contains all the
     // string
     for ( int i = 0; i < words.size(); i++) {
  
         // Intialise str as
         // empty
         string str = "" ;
  
         // length of string words[i]
         int l = words[i].length();
         for ( int j = 0; j < l; j++) {
  
             // For every uppercase
             // letter found map
             // that uppercase to
             // original words
             if (words[i][j] >= 'A'
                 && words[i][j] <= 'Z' ) {
                 str += words[i][j];
                 map[str].push_back(words[i]);
             }
         }
     }
  
     bool wordFound = false ;
  
     // Traverse the map for pattern
     // matching
     for ( auto & it : map) {
  
         // If pattern matches then
         // print the corresponding
         // mapped words
         if (it.first == pattern) {
             wordFound = true ;
             for ( auto & itt : it.second) {
                 cout << itt << endl;
             }
         }
     }
  
     // If word not found print
     // "No match found"
     if (!wordFound) {
         cout << "No match found" ;
     }
}
  
// Driver's Code
int main()
{
     vector<string> words = {
         "Hi" , "Hello" , "HelloWorld" , "HiTech" , "HiGeek" , "HiTechWorld" , "HiTechCity" , "HiTechLab"
     };
  
     // Pattern to be found
     string pattern = "HT" ;
  
     // Function call to find the
     // words that match to the
     // given pattern
     CamelCase(words, pattern);
  
     return 0;
}

Java

// Java to find CamelCase Pattern
// matching
import java.util.*;
  
class GFG{
   
// Function that prints the camel
// case pattern matching
static void CamelCase(ArrayList<String> words, String pattern)
{
   
     // Map to store the hashing
     // of each words with every
     // uppercase letter found
     Map<String, List<String>> map = new HashMap<String, List<String>>();
   
     // Traverse the words array
     // that contains all the
     // String
     for ( int i = 0 ; i < words.size(); i++) {
   
         // Intialise str as
         // empty
         String str = "" ;
   
         // length of String words[i]
         int l = words.get(i).length();
         for ( int j = 0 ; j < l; j++) {
   
             // For every uppercase
             // letter found map
             // that uppercase to
             // original words
             if (words.get(i).charAt(j) >= 'A'
                 && words.get(i).charAt(j) <= 'Z' ) {
                 str += words.get(i).charAt(j);
                 map.put(str, list(map.get(str), words.get(i)));
             }
         }
     }
   
     boolean wordFound = false ;
   
     // Traverse the map for pattern
     // matching
     for (Map.Entry<String, List<String>> it : map.entrySet()) {
   
         // If pattern matches then
         // print the corresponding
         // mapped words
         if (it.getKey().equals(pattern)) {
             wordFound = true ;
             for (String s : it.getValue())
             System.out.print(s + "\n" );
              
         }
     }
   
     // If word not found print
     // "No match found"
     if (!wordFound) {
         System.out.print( "No match found" );
     }
}
   
private static List<String> list(List<String> list, String str) {
     List<String> temp = new ArrayList<String>();
     if (list != null )
         temp.addAll(list);
     temp.add(str);
     return temp;
}
  
// Driver's Code
public static void main(String[] args)
{
     String arr[] = { "Hi" , "Hello" , "HelloWorld" , "HiTech" , "HiGeek" , "HiTechWorld" , "HiTechCity" , "HiTechLab"
         };
  
     ArrayList<String> words = new ArrayList<String>(Arrays.asList(arr));
   
     // Pattern to be found
     String pattern = "HT" ;
   
     // Function call to find the
     // words that match to the
     // given pattern
     CamelCase(words, pattern);
   
}
}
  
// This code is contributed by PrinciRaj1992

Python3

# Python3 to find CamelCase Pattern 
# matching 
  
# Function that prints the camel 
# case pattern matching 
def CamelCase(words, pattern) :
  
     # Map to store the hashing 
     # of each words with every 
     # uppercase letter found 
     map = dict .fromkeys(words, None ); 
  
     # Traverse the words array 
     # that contains all the 
     # string 
     for i in range ( len (words)) :
  
         # Intialise str as 
         # empty 
         string = ""; 
  
         # length of string words[i] 
         l = len (words[i]); 
         for j in range (l) :
  
             # For every uppercase 
             # letter found map 
             # that uppercase to 
             # original words 
             if (words[i][j] > = 'A' and words[i][j] < = 'Z' ) :
                 string + = words[i][j]; 
                  
                 if string not in map :
                     map [string] = [words[i]]
                      
                 elif map [string] is None :
                     map [string] = [words[i]]
                      
                 else :
                     map [string].append(words[i]); 
  
     wordFound = False ; 
  
     # Traverse the map for pattern 
     # matching 
     for key, value in map .items() :
  
         # If pattern matches then 
         # print the corresponding 
         # mapped words 
         if (key = = pattern) :
             wordFound = True ; 
             for itt in value :
                 print (itt); 
  
     # If word not found print 
     # "No match found" 
     if ( not wordFound) :
         print ( "No match found" ); 
   
  
# Driver's Code 
if __name__ = = "__main__" : 
  
     words = [
         "Hi" , "Hello" , "HelloWorld" , "HiTech" , "HiGeek" , "HiTechWorld" , "HiTechCity" , "HiTechLab"
     ]; 
  
     # Pattern to be found 
     pattern = "HT" ; 
  
     # Function call to find the 
     # words that match to the 
     # given pattern 
     CamelCase(words, pattern); 
      
# This code is contributed by AnkitRai01

C#

// C# to find CamelCase Pattern
// matching
using System;
using System.Collections.Generic;
  
class GFG{
    
// Function that prints the camel
// case pattern matching
static void CamelCase(List<String> words, String pattern)
{
    
     // Map to store the hashing
     // of each words with every
     // uppercase letter found
     Dictionary<String, List<String>> map = new Dictionary<String, List<String>>();
    
     // Traverse the words array
     // that contains all the
     // String
     for ( int i = 0; i < words.Count; i++) {
    
         // Intialise str as
         // empty
         String str = "" ;
    
         // length of String words[i]
         int l = words[i].Length;
         for ( int j = 0; j < l; j++) {
    
             // For every uppercase
             // letter found map
             // that uppercase to
             // original words
             if (words[i][j] >= 'A'
                 && words[i][j] <= 'Z' ) {
                 str += words[i][j];
                 if (map.ContainsKey(str))
                     map[str] = list(map[str], words[i]);
                 else
                     map.Add(str, list( null , words[i]));
             }
         }
     }
    
     bool wordFound = false ;
    
     // Traverse the map for pattern
     // matching
     foreach (KeyValuePair<String, List<String>> it in map) {
         // If pattern matches then
         // print the corresponding
         // mapped words
         if (it.Key.Equals(pattern)) {
             wordFound = true ;
             foreach (String s in it.Value)
             Console.Write(s + "\n" );
               
         }
     }
    
     // If word not found print
     // "No match found"
     if (!wordFound) {
         Console.Write( "No match found" );
     }
}
    
private static List<String> list(List<String> list, String str) {
     List<String> temp = new List<String>();
     if (list != null )
         temp.AddRange(list);
     temp.Add(str);
     return temp;
}
   
// Driver's Code
public static void Main(String[] args)
{
     String []arr = { "Hi" , "Hello" , "HelloWorld" , "HiTech" , "HiGeek" , "HiTechWorld" , "HiTechCity" , "HiTechLab"
         };
   
     List<String> words = new List<String>(arr);
    
     // Pattern to be found
     String pattern = "HT" ;
    
     // Function call to find the
     // words that match to the
     // given pattern
     CamelCase(words, pattern);
    
}
}
  
// This code is contributed by Rajput-Ji

输出如下：

HiTech
HiTechWorld
HiTechCity
HiTechLab

时间复杂度：O(N * M), 其中N是包含字符串的列表的长度, M是最长字符串的长度。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: