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.

// 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;
    }
};

Java

• Java
• C++
• Python

• 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;
      }
  }
  

• // 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)
  

All Problems

All Solutions