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

# 🚀 _2. CamelCase Pattern Matching_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/string-bonus-problems/problem/camelcase-pattern-matching2259)

## 💡 **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)

```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)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>