LeetCode 1023. Camelcase Matching

原题链接在这里: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. 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.

题解:

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 }

 

上一篇:FTP主被动模式


下一篇:【PAT甲级】1023 Have Fun with Numbers (20 分)