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 <= 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.
-
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; }