Leetcode 1023. Camelcase Matching

Problem Explanation:

The problem requires us to determine whether each of the given queries matches the given pattern. A query matches the pattern if we can insert lowercase letters to the pattern word so that it equals the query. We may insert each character at any position, and we may also not insert any characters.

The input is a list of queries and a pattern, and we are expected to return a list of boolean values. In this output list, each Boolean value at index i corresponds to whether the query at index i in the queries list matches the pattern.

Let's consider Example #1:

For this example, the queries list is ["FooBar", "FooBarTest", "FootBall", "FrameBuffer", "ForceFeedBack"], and the pattern is "FB".

The output for this example is [true, false, true, true, false]. This is because the queries "FooBar", "FootBall", and "FrameBuffer" can be generated from the pattern by inserting certain lowercase letters at appropriate positions, but the queries "FooBarTest" and "ForceFeedBack" cannot.

Approach to Solution:

In terms of the approach used in the solution, we essentially apply a linear search through each query in the list. For each query, we check if the uppercase characters match the pattern since the lowercase characters can be inserted at any position. If an uppercase character in the query does not match the current character in the pattern, then we return false. Here's the algorithm in steps:

1. For each query in the queries list:
   • Initialize j to 0 (this will keep track of the current position in the pattern).
   • For each character, c, in the query string:
     • If j < length of pattern and c matches the current character in the pattern, then increment j. This means we have found a matching character in the pattern.
     • Otherwise, if c is an uppercase letter, then we return false because the pattern does not match the query at this point.
2. After the loop, if j equals the length of the pattern, we return true, else we return false.

The time complexity of this solution is O(n), where n is the total number of characters in the queries list.

Python Solution:

1
2python
3class Solution:
4    def camelMatch(self, queries, pattern) -> [bool]:
5        def isMatch(query):
6            j = 0
7            for c in query:
8                if j < len(pattern) and c == pattern[j]:
9                    j += 1
10                elif c.isupper():
11                    return False
12            return j == len(pattern)
13        
14        return [isMatch(query) for query in queries]

Java Solution:

1
2java
3class Solution {
4    public List<Boolean> camelMatch(String[] queries, String pattern) {
5        List<Boolean> res = new ArrayList<>();
6        for (String query : queries) {
7            res.add(isMatch(query, pattern));
8        }
9        return res;
10    }
11
12    private boolean isMatch(String query, String pattern) {
13        int j = 0;
14        for (char c : query.toCharArray()) {
15            if (j < pattern.length() && c == pattern.charAt(j)) {
16                j++;
17            } else if (c >= 'A' && c <= 'Z') {
18                return false;
19            }
20        }
21        return j == pattern.length();
22    }
23}

JavaScript Solution:

1
2javascript
3/**
4 * @param {string[]} queries
5 * @param {string} pattern
6 * @return {boolean[]}
7 */
8var camelMatch = function(queries, pattern) {
9    return queries.map(query => isMatch(query, pattern));
10};
11
12function isMatch(query, pattern) {
13    let j = 0;
14    for (let c of query) {
15        if (j < pattern.length && c === pattern[j]) {
16            j++;
17        } else if (c === c.toUpperCase()) {
18            return false;
19        }
20    }
21    return j === pattern.length;
22}

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<bool> camelMatch(vector<string>& queries, string pattern) {
6        vector<bool> res;
7        for (string& query : queries) {
8            res.push_back(isMatch(query, pattern));
9        }
10        return res;
11    }
12    
13private:
14    bool isMatch(string& query, string& pattern) {
15        int j = 0;
16        for (char c : query) {
17            if (j < pattern.size() && c == pattern[j]) {
18                j++;
19            } else if (isupper(c)) {
20                return false;
21            }
22        }
23        return j == pattern.size();
24    }
25};

C# Solution:

1
2csharp
3public class Solution {
4    public IList<bool> CamelMatch(string[] queries, string pattern) {
5        var res = new List<bool>(queries.Length);
6        foreach (var query in queries) {
7            res.Add(IsMatch(query, pattern));
8        }
9        return res;
10    }
11    
12    private bool IsMatch(string query, string pattern) {
13        int j = 0;
14        foreach (char c in query) {
15            if (j < pattern.Length && c == pattern[j]) {
16                j++;
17            } else if (char.IsUpper(c)) {
18                return false;
19            }
20        }
21        return j == pattern.Length;
22    }
23}

Ruby Solution:

1
2ruby
3class Solution
4    def camelMatch(queries, pattern)
5        result = Array.new
6        queries.each {|query| result.push(isMatch(query, pattern))}
7        return result
8    end
9
10    def isMatch(query, pattern)
11        j = 0
12        query.each_char do |c|
13            if j < pattern.length and c == pattern[j]
14                j += 1
15            elsif c >= "A" and c <= "Z"
16                return false
17            end
18        end
19        return j == pattern.length
20    end
21end

Go Solution:

1
2go
3func camelMatch(queries []string, pattern string) []bool {
4    result := make([]bool, len(queries))
5    for i, query := range queries {
6        result[i] = isMatch(query, pattern)
7    }
8    return result
9}
10
11func isMatch(query string, pattern string) bool {
12    j := 0
13    for _, c := range query {
14        if j < len(pattern) && c == rune(pattern[j]) {
15            j++
16        } else if c >= 'A' && c <= 'Z' {
17            return false
18        }
19    }
20    return j == len(pattern)
21}

The algorithm described above works best for this specific scenario - matching camel-case terms. However, for a broader range of pattern-matching requirements, one can consider applying a string-searching algorithm, such as the Knuth-Morris-Pratt (KMP) or the Rabin-Karp algorithm. These pattern-matching solutions provide a robust approach, handling both straightforward and complex problems. These utilize a combination of preprocessing techniques and search algorithms to address the problem more efficiently.

Conclusion:

In summary, this pattern-matching problem involves a careful inspection of strings. One has to accurately link the matching uppercase characters in the queries with the given pattern and discriminate against any outlying uppercase characters not present in the pattern. Each of the Python, Java, JavaScript, C++, C#, Ruby, and Go solutions presented utilizes the same approach - highlighting the conceptual and algorithmic similarities transcending diverse programming languages.