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 <= queries.length <= 100
1 <= queries[i].length <= 100
1 <= pattern.length <= 100
- All strings consists only of lower and upper case English letters.
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
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;
}
}