2. CamelCase Pattern Matching.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	String Trie Advanced Data Structure

🚀 2. CamelCase Pattern Matching 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given a dictionary of words arr[], where each word follows CamelCase notation, print all words in the dictionary that match with a given pattern pat consisting of uppercase characters only.

CamelCase notation is the practice of writing compound words or phrases such that each word or abbreviation begins with a capital letter. Examples of CamelCase include "PowerPoint", "Wikipedia", "GeeksForGeeks", etc.

For example:

• "GeeksForGeeks" matches the pattern "GFG" because if we extract all the uppercase letters from "GeeksForGeeks", we get "GFG".
• However, it does not match the pattern "FG" because the first letter of the pattern is "F", but the first uppercase letter in the word is "G".

Note: The driver code will sort your answer before checking and will return the result in any order.

🔍 Example Walkthrough:

Input:

arr[] = ["WelcomeGeek", "WelcomeToGeeksForGeeks", "GeeksForGeeks"], pat = "WTG"

Output:

["WelcomeToGeeksForGeeks"]

Explanation:
Only "WelcomeToGeeksForGeeks" matches the pattern "WTG" as it contains the uppercase letters "W", "T", and "G".

Input:

arr[] = ["Hi", "Hello", "HelloWorld", "HiTech", "HiGeek", "HiTechWorld", "HiTechCity", "HiTechLab"], pat = "HA"

Output:

[]

Explanation:
None of the words match the given pattern "HA".

Constraints:

• $1 \leq \text{arr.size()} \leq 1000$
• $1 \leq \text{pat.size()} \leq 100$
• $1 \leq \text{arr[i].size()} \leq 100$

🎯 My Approach:

Step-by-Step:

1. Iterate through the Words in the Array:
   For each word in the dictionary, traverse it to extract the uppercase characters.

2. Compare Uppercase Letters with the Pattern:
   For each word, extract the uppercase letters and compare them with the given pattern. If the uppercase letters of the word match the entire pattern, then that word is a valid match.

3. Add Matching Words to the Result List:
   If the word's uppercase letters match the pattern, add it to the result list.

4. Return the Result List:
   Return the list of words that matched the pattern.

🕒 Time and Auxiliary Space Complexity:

• Time Complexity: O(n * m), where n is the number of words in the dictionary and m is the maximum length of a word. We loop over each word in the array and check its uppercase letters.

• Auxiliary Space Complexity: O(n), where n is the number of words in the result list, as we store matching words.

📝 Solution Code

Code (Cpp)

class Solution {
public:
    vector<string> camelCase(const vector<string> &arr, const string &pat) {
        vector<string> res;

        for (const string &word : arr) {
            int j = 0;
            for (int i = 0; i < word.size(); ++i) {
                if (isupper(word[i])) {
                    if (j < pat.length() && word[i] == pat[j]) {
                        j++; 
                    } else if (j < pat.length()) {
                        break; 
                    }
                }
            }
            if (j == pat.length()) {
                res.push_back(word);
            }
        }

        return res;
    }
};

Code (Java)

class Solution {
    public List<String> camelCase(String[] arr, String pat) {
        List<String> res = new ArrayList<>();
        for (String word : arr) {
            int j = 0;
            for (int i = 0; i < word.length(); ++i) {
                if (Character.isUpperCase(word.charAt(i))) {
                    if (j < pat.length() && word.charAt(i) == pat.charAt(j)) {
                        j++;
                    } else if (j < pat.length()) {
                        break;
                    }
                }
            }
            if (j == pat.length()) {
                res.add(word);
            }
        }
        return res;
    }
}

Code (Python)

class Solution:
    
    def camelCase(self, arr, pat):
        res = []
        for word in arr:
            j = 0
            for i in range(len(word)):
                if word[i].isupper():
                    if j < len(pat) and word[i] == pat[j]:
                        j += 1
                    elif j < len(pat):
                        break
            if j == len(pat):
                res.append(word)
        return res

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count