Given a list of words where each word follows CamelCase notation, the task is to print all words in the dictionary that match with a given pattern consisting of uppercase characters only.
Examples
Input: arr[] = [ “WelcomeGeek”, “WelcomeToGeeksForGeeks”, “GeeksForGeeks” ], pattern = “WTG”
Output: WelcomeToGeeksForGeeks
Explanation:
There is only one abbreviation for the given pattern i.e., WelcomeToGeeksForGeeks.Input: arr[] = [ “Hi”, “Hello”, “HelloWorld”, “HiTech”, “HiGeek”, “HiTechWorld”, “HiTechCity”, “HiTechLab” ], pattern = “HA”
Output: No match found
Explanation:
There is no such abbreviation for the given pattern.
Approach:
1. Traverse through every word and keep Hashing that word with every uppercase letter found in the given string.
For Example:
For string = "GeeksForGeeks"
then the hashing after every uppercase letter found is:
map {
{G, GeeksForGeeks},
{GF, GeeksForGeeks},
{GFG, GeeksForGeeks}
}
2. After creating hashing for all the string in the list. Search for the given pattern in the map and print all the string mapped to it.
Below is the implementation of the above approach:
C++
// C++ to find CamelCase Pattern// matching#include "bits/stdc++.h"using namespace std;// Function that prints the camel// case pattern matchingvoid 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++) { // Initialise 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 Codeint 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// matchingimport 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++) { // Initialise 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 matchingdef 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)): # Initialise 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 Codeif __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// matchingusing 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++) { // Initialise 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 |
Javascript
// JavaScript to find CamelCase Pattern// matchingconst CamelCase = (words, pattern) => { // Map to store the hashing // of each words with every // uppercase letter found const map = new Map(); // Traverse the words array // that contains all the // String for (let i = 0; i < words.length; i++) { // Initialise str as // empty let str = ""; // length of String words[i] const l = words[i].length; for (let 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.has(str)) { const list = map.get(str); list.push(words[i]); map.set(str, list); } else { map.set(str, [words[i]]); } } } } let wordFound = false |
Output
HiTech HiTechWorld HiTechCity HiTechLab
Time Complexity: O(N*M) where N is the length of the list containing the strings and M is the length of the longest string.
Auxiliary Space: O(N*M)
Efficient Approach 1:
Step-by-step approach:
- Prepare a string by concatenating all array elements & semicolon as a delimiter after every array element.
- Traverse through concatenated string and look for Upper Case characters or delimiter.
- Hold a temporary string with all Upper Case characters until delimiter comes in traversal. Add this temporary string as a key (if key doesn’t exist) in dictionary or append the word if key already exists.
- Once delimiter reached, reset the temporary variables.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;void PrintMatchingCamelCase(vector<string> arr, string pattern){ // Concatenating all array elements // using Aggregate function of LINQ // putting semicolon as delimiter after each element string cctdString = ""; for (int i = 0; i < arr.size(); i++) { cctdString += arr[i]; if (i != arr.size() - 1) cctdString.push_back(';'); } // Map to store the hashing // of each words with every // uppercase letter found unordered_map<string, vector<string> > maps; // temporary Variables int charPos = 0; int wordPos = 0; string strr = ""; // Traversing through concatenated String for (; charPos < cctdString.length(); charPos++) { // Identifying if the current Character is // CamelCase If so, then adding to map // accordingly if (cctdString[charPos] >= 'A' && cctdString[charPos] <= 'Z') { strr += cctdString[charPos]; // If pattern matches then // print the corresponding // mapped words if (maps.find(strr) != maps.end()) { vector<string> temp; temp.insert(temp.end(), maps[strr].begin(), maps[strr].end()); temp.push_back(arr[wordPos]); maps[strr] = temp; } else { vector<string> vec = { arr[wordPos] }; maps[strr] = vec; } } // If delimiter has reached then resetting // temporary string also incrementing word // position value else if (cctdString[charPos] == ';') { wordPos++; strr = ""; } } // If pattern matches then // print the corresponding // mapped words if (maps.find(pattern) != maps.end()) { for (int i = 0; i < maps[pattern].size(); i++) { cout << maps[pattern][i] << endl; } } else { cout << "No Match Found" << endl; }}// Driver codeint main(){ // Array of words vector<string> arr = { "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 PrintMatchingCamelCase(arr, pattern);}// This code is contributed by parthmanchanda81 |
Java
// Java Code for above approachimport java.util.*;public class Solution { static void PrintMatchingCamelCase(String[] arr, String pattern) { // Concatenating all array elements // using Aggregate function of LINQ // putting semicolon as delimiter after each element String cctdString = ""; for (int i = 0; i < arr.length; i++) { cctdString += arr[i]; if (i != arr.length - 1) cctdString += ';'; } // Map to store the hashing // of each words with every // uppercase letter found HashMap<String, ArrayList<String> > maps = new HashMap<>(); // temporary Variables int charPos = 0; int wordPos = 0; String strr = ""; // Traversing through concatenated String for (; charPos < cctdString.length(); charPos++) { // Identifying if the current Character is // CamelCase If so, then adding to map // accordingly if (cctdString.charAt(charPos) >= 'A' && cctdString.charAt(charPos) <= 'Z') { strr += cctdString.charAt(charPos); // If pattern matches then // print the corresponding // mapped words if (maps.containsKey(strr)) { ArrayList<String> temp = new ArrayList<>(); temp = maps.getOrDefault( strr, new ArrayList<>()); temp.add(arr[wordPos]); maps.put(strr, temp); } else { ArrayList<String> temp = new ArrayList<>(); temp.add(arr[wordPos]); maps.put(strr, temp); } } // If delimiter has reached then resetting // temporary string also incrementing word // position value else if (cctdString.charAt(charPos) == ';') { wordPos++; strr = ""; } } // If pattern matches then // print the corresponding // mapped words if (maps.containsKey(pattern)) { for (int i = 0; i < maps.getOrDefault(pattern, new ArrayList<>()) .size(); i++) { System.out.println( maps.get(pattern).get(i)); } } else { System.out.println("No Match Found"); } } // Driver code public static void main(String[] args) { // Array of words String[] arr = { "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 PrintMatchingCamelCase(arr, pattern); }}// This code is contributed by karandeep1234 |
Python3
def PrintMatchingCamelCase(arr, pattern): # Concatenating all array elements # using Aggregate function of LINQ # putting semicolon as delimiter after each element cctdString = ';'.join(arr) # Map to store the hashing # of each words with every # uppercase letter found maps = dict() # temporary Variables wordPos = 0 strr = "" # Traversing through concatenated String for charPos in range(len(cctdString)): # Identifying if the current Character is # CamelCase If so, then adding to map # accordingly if (cctdString[charPos] >= 'A' and cctdString[charPos] <= 'Z'): strr += cctdString[charPos] # If pattern matches then # print the corresponding # mapped words if strr in maps: temp = [] temp.extend(maps[strr]) temp.append(arr[wordPos]) maps[strr] = temp else: vec = [arr[wordPos], ] maps[strr] = vec # If delimiter has reached then resetting # temporary string also incrementing word # position value elif (cctdString[charPos] == ';'): wordPos += 1 strr = "" # If pattern matches then # print the corresponding # mapped words if (pattern in maps): for i in range(len(maps[pattern])): print(maps[pattern][i]) else: print("No Match Found")# Driver codeif __name__ == '__main__': # Array of words arr = ["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 PrintMatchingCamelCase(arr, pattern)# This code is contributed by Amartya Ghosh |
C#
using System;using System.Collections.Generic;using System.Linq;public class GFG { public static void PrintMatchingCamelCase(String[] arr, String pattern) { // Concatenating all array elements // using Aggregate function of LINQ // putting semicolon as delimiter after each element String cctdString = arr.Aggregate((i, j) = > i + ';' + j); // Map to store the hashing // of each words with every // uppercase letter found Dictionary<String, List<String> > map = new Dictionary<string, List<string> >(); // temporary Variables int charPos = 0; int wordPos = 0; string strr = string.Empty; // Traversing through concatenated String for (; charPos < cctdString.Length; charPos++) { // Identifying if the current Character is // CamelCase If so, then adding to map // accordingly if (cctdString[charPos] >= 'A' && cctdString[charPos] <= 'Z') { strr += cctdString[charPos]; if (map.ContainsKey(strr)) { List<String> temp = new List<string>(); temp.AddRange(map[strr]); temp.Add(arr[wordPos]); map[strr] = temp; } else { map.Add(strr, new List<string>{ arr[wordPos] }); } } // If delimiter has reached then resetting // temporary string also incrementing word // position value else if (cctdString[charPos] == ';') { wordPos++; strr = string.Empty; } } // If pattern matches then // print the corresponding // mapped words if (map.ContainsKey(pattern)) { foreach(String word in map[pattern]) { Console.WriteLine(word); } } else { Console.WriteLine("No Match Found"); } } // Driver's Code public static void Main(String[] args) { // Array of Words String[] arr = { "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 PrintMatchingCamelCase(arr, pattern); } // This code is contributed by Rishabh Singh} |
Javascript
// Javascript ptogram for the above approachfunction PrintMatchingCamelCase(arr, pattern) { // Concatenating all array elements // using semicolon as delimiter after each element let cctdString = arr.join(';'); // Map to store the hashing // of each words with every // uppercase letter found let maps = {}; // temporary Variables let wordPos = 0; let strr = ''; // Traversing through concatenated String for (let charPos = 0; charPos < cctdString.length; charPos++) { // Identifying if the current Character is // CamelCase If so, then adding to map // accordingly if ( cctdString[charPos] >= 'A' && cctdString[charPos] <= 'Z' ) { strr += cctdString[charPos]; // If pattern matches then // print the corresponding // mapped words if (strr in maps) { let temp = []; temp = temp.concat(maps[strr]); temp.push(arr[wordPos]); maps[strr] = temp; } else { let vec = [arr[wordPos]]; maps[strr] = vec; } } else if (cctdString[charPos] === ';') { // If delimiter has reached then resetting // temporary string also incrementing word // position value wordPos += 1; strr = ''; } } // If pattern matches then // print the corresponding // mapped words if (pattern in maps) { for (let i = 0; i < maps[pattern].length; i++) { console.log(maps[pattern][i]); } } else { console.log('No Match Found'); }}// Driver codelet arr = [ 'Hi', 'Hello', 'HelloWorld', 'HiTech', 'HiGeek', 'HiTechWorld', 'HiTechCity', 'HiTechLab'];// Pattern to be foundlet pattern = 'HT';// Function call to find the// words that match to the// given patternPrintMatchingCamelCase(arr, pattern);// This code is contributed by codebraxnzt |
Output
HiTech HiTechWorld HiTechCity HiTechLab
Time Complexity: O(N*|S|) N is size of array and |S| is max size of word in array.
Auxiliary Space: O(N)
Efficient Approach 2:
Step-by-step approach:
- Traverse through every word of given vector of string.
- For each word we initialize a variable x = 0 which indicate the index of pattern to be matched.
- Traverse the each word, if the character of word matched with x’th character of pattern then increment x, else if the character is not match and uppercase then further solution is not possible.
- If we able to match all character of pattern then add into our solution.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;void PrintMatchingCamelCase(vector<string> arr, string pattern){ // vector for storing matched word vector<string> ans; for (int i = 0; i < arr.size(); i++) { int x = 0; for (int j = 0; j < arr[i].size(); j++) { // if character is matched with pattern // character if (x < pattern.size() && pattern[x] == arr[i][j]) { x++; } // character not matched but uppercase else if (isupper(arr[i][j])) break; } // if matched all the character then take the word // into the ans vector if (x == pattern.size()) { ans.push_back(arr[i]); } } // If no matched found if (ans.size() == 0) { cout << "No Match Found" << endl; } else { // print all matched word for (int i = 0; i < ans.size(); i++) { cout << ans[i] << endl; } }}// Driver codeint main(){ // Array of words vector<string> arr = { "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 PrintMatchingCamelCase(arr, pattern);}// This code is contributed by Dipak Prasad Gupta |
Python3
import re# Function call to find the# words that match to the# given patterndef PrintMatchingCamelCase(arr, pattern): # array for storing matched word ans = [] for word in arr: x = 0 for letter in word: # if character is matched with pattern character if x < len(pattern) and pattern[x] == letter: x += 1 # character not matched but uppercase elif letter.isupper(): break # if matched all the character then take the word into # the ans array if x == len(pattern): ans.append(word) # If no matched found if len(ans) == 0: print("No Match Found") # print all matched word else: for word in ans: print(word)# Test casearr = ["Hi", "Hello", "HelloWorld", "HiTech", "HiGeek", "HiTechWorld", "HiTechCity", "HiTechLab"]pattern = "HT"PrintMatchingCamelCase(arr, pattern) |
C#
using System;using System.Collections.Generic;public class GFG { // Function to find and print the words that match the // given pattern public static void PrintMatchingCamelCase(List<string> arr, string pattern) { List<string> ans = new List<string>(); // Iterate through each word in the array foreach(string word in arr) { int x = 0; // Check each character in the word foreach(char letter in word) { // If the character matches the pattern // character, move to the next pattern // character if (x < pattern.Length && pattern[x] == letter) { x++; } // If the character doesn't match but is // uppercase, break the inner loop else if (char.IsUpper(letter)) { break; } } // If all pattern characters were matched, add // the word to the 'ans' list if (x == pattern.Length) { ans.Add(word); } } // If no matched words found, print "No Match Found" if (ans.Count == 0) { Console.WriteLine("No Match Found"); } // Otherwise, print all matched words else { foreach(string word in ans) { Console.WriteLine(word); } } } public static void Main() { List<string> arr = new List<string>{ "Hi", "Hello", "HelloWorld", "HiTech", "HiGeek", "HiTechWorld", "HiTechCity", "HiTechLab" }; string pattern = "HT"; // Call the function to find and print the matching // camel case words PrintMatchingCamelCase(arr, pattern); }} |
Javascript
// Function call to find the// words that match to the// given patternconst PrintMatchingCamelCase = (arr, pattern) => { // array for storing matched word let ans = []; for (let i = 0; i < arr.length; i++) { let x = 0; for (let j = 0; j < arr[i].length; j++) { // if character is matched with pattern character if (x < pattern.length && pattern[x] === arr[i][j]) { x++; } // character not matched but uppercase else if (arr[i][j] === arr[i][j].toUpperCase()) { break; } } // if matched all the character then take the word // into the ans array if (x === pattern.length) { ans.push(arr[i]); } } // If no matched found if (ans.length === 0) { console.log("No Match Found"); } // print all matched word else { for (let i = 0; i < ans.length; i++) { console.log(ans[i]); } }};const arr = [ "Hi", "Hello", "HelloWorld", "HiTech", "HiGeek", "HiTechWorld", "HiTechCity", "HiTechLab"];const pattern = "HT";PrintMatchingCamelCase(arr, pattern); |
Output
HiTech HiTechWorld HiTechCity HiTechLab
Time Complexity: O(N*|S|) N is size of array and |S| is max size of word in array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
