Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1023.html

1023. Camelcase Matching (Medium)

A query word matches a given 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 may insert 0 characters.)

Given a list of queries, and a pattern, return an answer list of booleans, where answer[i] is true if and only if queries[i] matches the pattern.

 

Example 1:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]
Explanation: 
"FooBar" can be generated like this "F" + "oo" + "B" + "ar".
"FootBall" can be generated like this "F" + "oot" + "B" + "all".
"FrameBuffer" can be generated like this "F" + "rame" + "B" + "uffer".

Example 2:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBa"
Output: [true,false,true,false,false]
Explanation: 
"FooBar" can be generated like this "Fo" + "o" + "Ba" + "r".
"FootBall" can be generated like this "Fo" + "ot" + "Ba" + "ll".

Example 3:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FoBaT"
Output: [false,true,false,false,false]
Explanation: 
"FooBarTest" can be generated like this "Fo" + "o" + "Ba" + "r" + "T" + "est".

 

Note:

  1. 1 <= queries.length <= 100
  2. 1 <= queries[i].length <= 100
  3. 1 <= pattern.length <= 100
  4. All strings consists only of lower and upper case English letters.

Related Topics:
String, Trie

Solution 1.

  • class Solution {
        public List<Boolean> camelMatch(String[] queries, String pattern) {
            List<Boolean> camelMatchList = new ArrayList<Boolean>();
            int length = queries.length;
            for (int i = 0; i < length; i++) {
                String query = queries[i];
                camelMatchList.add(isSubsequenceAndCamelcase(pattern, query));
            }
            return camelMatchList;
        }
    
        public boolean isSubsequenceAndCamelcase(String pattern, String query) {
            int length1 = pattern.length(), length2 = query.length();
            int index1 = 0, index2 = 0;
            while (index1 < length1 && index2 < length2) {
                char c1 = pattern.charAt(index1), c2 = query.charAt(index2);
                index2++;
                if (c1 == c2)
                    index1++;
                else {
                    if (c2 <= 'Z')
                        return false;
                }
            }
            while (index2 < length2) {
                char c2 = query.charAt(index2);
                index2++;
                if (c2 <= 'Z')
                    return false;
            }
            return index1 == length1;
        }
    }
    
    ############
    
    class Solution {
        public List<Boolean> camelMatch(String[] queries, String pattern) {
            List<Boolean> ans = new ArrayList<>();
            for (var q : queries) {
                ans.add(check(q, pattern));
            }
            return ans;
        }
    
        private boolean check(String s, String t) {
            int m = s.length(), n = t.length();
            int i = 0, j = 0;
            for (; j < n; ++i, ++j) {
                while (i < m && s.charAt(i) != t.charAt(j) && Character.isLowerCase(s.charAt(i))) {
                    ++i;
                }
                if (i == m || s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            }
            while (i < m && Character.isLowerCase(s.charAt(i))) {
                ++i;
            }
            return i == m;
        }
    }
    
  • // OJ: https://leetcode.com/problems/camelcase-matching/
    // Time: O(QP)
    // Space: O(1)
    class Solution {
        bool match(string &s, string &p) {
            int i = 0, N = p.size();
            for (char c : s) {
                if (i == N) {
                    if (isupper(c)) return false;
                } else if (isupper(p[i])) {
                    if (islower(c)) continue;
                    if (c != p[i++]) return false;
                } else if (c != p[i]) continue;
                else ++i;
            }
            return i == N;
        }
    public:
        vector<bool> camelMatch(vector<string>& queries, string pattern) {
            vector<bool> ans;
            for (auto &s : queries) ans.push_back(match(s, pattern));
            return ans;
        }
    };
    
  • class Solution(object):
        def camelMatch(self, queries, pattern):
            """
            :type queries: List[str]
            :type pattern: str
            :rtype: List[bool]
            """
            import re
            ps = re.findall("[A-Z][a-z]*", pattern)
            N = len(queries)
            res = []
            for q in queries:
                qs = re.findall("[A-Z][a-z]*", q)
                hasFind = False
                if len(ps) == len(qs):
                    if all(self.isSubSeq(q, p) for (q, p) in zip(qs, ps)):
                        hasFind = True
                res.append(hasFind)
            return res
        
        def isSubSeq(self, qu, pa):
            qu = iter(qu)
            return all(p in qu for p in pa)
    
  • func camelMatch(queries []string, pattern string) (ans []bool) {
    	check := func(s, t string) bool {
    		m, n := len(s), len(t)
    		i, j := 0, 0
    		for ; j < n; i, j = i+1, j+1 {
    			for i < m && s[i] != t[j] && (s[i] >= 'a' && s[i] <= 'z') {
    				i++
    			}
    			if i == m || s[i] != t[j] {
    				return false
    			}
    		}
    		for i < m && s[i] >= 'a' && s[i] <= 'z' {
    			i++
    		}
    		return i == m
    	}
    	for _, q := range queries {
    		ans = append(ans, check(q, pattern))
    	}
    	return
    }
    
  • function camelMatch(queries: string[], pattern: string): boolean[] {
        const check = (s: string, t: string) => {
            const m = s.length;
            const n = t.length;
            let i = 0;
            let j = 0;
            for (; j < n; ++i, ++j) {
                while (i < m && s[i] !== t[j] && s[i].codePointAt(0) >= 97) {
                    ++i;
                }
                if (i === m || s[i] !== t[j]) {
                    return false;
                }
            }
            while (i < m && s[i].codePointAt(0) >= 97) {
                ++i;
            }
            return i == m;
        };
        const ans: boolean[] = [];
        for (const q of queries) {
            ans.push(check(q, pattern));
        }
        return ans;
    }
    
    

All Problems

All Solutions