原题链接在这里:https://leetcode.com/problems/camelcase-matching/
题目:
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.
题解:
For each query, use two points to check if this query matches pattern.
For each char c in query, if it equals current i pointing char in pattern, move the pointer.
If not equal and c is uppercase, then either current i pointing char is lower case or uppercase, pattern can't insert any lowercase letter to match it. return false.
Check if i could comes to the end of pattern.
Time Complexity: O(n*m). n = queries.length. m is average length of queries and pattern.
Space: O(1). regardless res.
AC Java:
1 class Solution { 2 public List<Boolean> camelMatch(String[] queries, String pattern) { 3 List<Boolean> res = new ArrayList<>(); 4 for(String query : queries){ 5 res.add(isMatch(query, pattern)); 6 } 7 8 return res; 9 } 10 11 private boolean isMatch(String s, String p){ 12 int i = 0; 13 for(char c : s.toCharArray()){ 14 if(i<p.length() && p.charAt(i) == c){ 15 i++; 16 }else if(c>='A' && c<='Z'){ 17 return false; 18 } 19 } 20 21 return i == p.length(); 22 } 23 }