[leetcode] 1023. Camelcase Matching

[leetcode] 1023. Camelcase Matching

Description

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

分析

题目的意思是：给定一个字符串数组queries，和模板pattern，文queries里面的query能够匹配上pattern。这道题我看了一下提示，要用动态规划啥的，顿时傻了眼。后面才发现用双指针法也能搞定，看来我还需要沉淀。思想很简单，遍历queries，然后对每个字符用双指针和pattern进行匹配。

代码

class Solution: def match(self,p,q): n=len(q) j=0 for i in range(n): if(j List[bool]: res=[] for query in queries: t=self.match(pattern,query) res.append(t) return res

参考文献

​​[LeetCode] Python - Two Pointer - Memory usage less than 100%​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。