Given a list of string that represent class names in CamelCaseNotation and a pattern. Write a function that returns the matching elements as a list. Example:
List:['HelloMars','HelloWorld','HelloWorldMars','HiHo']
input: 'H'->output:['HelloMars','HelloWorld','HelloWorldMars','HiHo'];
input: 'HW'->output:['HelloWorld','HelloWorldMars'];
input:'Ho'->output:[];
input:'HeWorM'->output:['HelloWorldMars'].
给出一组符合“驼峰命名规则”的字符串和一个字符模板，返回一个包含所有符合这个模板的字符串的数组。至于怎样才算符合模板，请看上面的例子。
1. 询问
字符是不是都是大小写？假设是。
对空的模板如何处理？假设返回None。
输入是不是合法的？比如模板会不会有小写字母开头的情况？假设没有，并且输入都是合法的。
2. 分析
规律分析
这道题没有明显的暴力破解，而只要摸到规律，离解题其实也不远了。
假设字符都是大小写字母，那么可以把一个字符串看做由大写字母分割的一个字符串组，例如'HelloWorldMars'可以分割成为['Hello','World','Mars']。同样模板也可以这么分割。很明显，模板分割后的数组长度应该小于等于字符串组的长度，而且在其长度范围内，每一个元素都应该是字符串组的子串（这里认为相等也是子串的一种情况）。
对字符串进行如上描述的分割，复杂度应该是O(N)，N为字符串长度，因为要遍历整个字符串。假设给出的数组里面有k个字符串，那么都进行分割也就是k个O(Li)求和等于O(L)，L为长度之和。然后都和模板比较，生成模板的复杂度是O(H)假设模板长度为H，每次比较的复杂度为O(min(H, Li))，总体时间复杂度是比较复杂的一个东西。
优化
上面有一个很明显的浪费：假设模板字符串分解后长度为3，那么有必要对长度为999的字符串进行彻底分解吗？答案是没有必要。分解出两个以后，就可以使用其进行比较了。例如模板为ABC，字符串为ABCDEFG……，分解到[A,B,CDEFG……]即可。
那么，假如这个字符串分解后长度还是3，但是中间夹杂很多不需要的东西怎么办？模板为ABC，字符串大写字母也都是ABC，但是中间插了几万个小写字母？对于这个问题，我认为是没法优化的，因为那些小写字母都得看，万一不看冒出一个大写字母来，结果就错了。
在这一步，可以看到效率肯定提高了，但是复杂度不变，因为考虑的是最坏情况，还是整个字符串都得看。
然后比较。假如字符串结果的长度小于模板结果长度，没有必要比较，直接fail。然后通过上面那一步，保证长度都是一样的，也就是说是O(H)。同样，这个也没得优化，必须按照模板一个个比较下去，否则万一里面有一个不一样，结果是否。
因此，最后的时间复杂度为O(kH+L)，空间复杂度是O（H+L）。
发散
上面的解法用了额外空间，有没有可能不需要额外空间，直接拿出两个字符串比较？
如果是那样，可能要用到双指针，一个指向模板，一个指向字符串，本质上逻辑和分组的方法一样，先比较完模板里面的一组，然后移动指针到下一组开始的地方继续比较。因为情况很多，最坏情况下时间复杂度是O(H+Li)，k次也就是O(kH+L)。这种方法总体而言空间效率更好。当然，代码更难写。前面那个解法，就是按照大写字母分组稍微麻烦一些，之后都是很简单的编程。
不过既然有更好的解法，就写这个吧。
3. 代码
class Solution:
def stringPattern(self, p, list):
if not p or not list:
return None
res = []
for s in list:
if self.isMatch(p, s):
res.append(s)
return res
def isMatch(self, p, s):
if not s:
return False
p1 = p2 = 0
while p1 < len(p) and p2 < len(s):
# compare first upper char
if p[p1] != s[p2]:
return False
else:
p1 += 1
p2 += 1
# compare rest lower char
while p1 < len(p) and p2 < len(s):
# if found next upper char, break
if 'A' <= p[p1] <= 'Z':
break
else:
if p[p1] != s[p2]:
return False
else:
p1 += 1
p2 += 1
# s skip until next upper char
while p2 < len(s) and not 'A' <= s[p2] <= 'Z':
p2 += 1
if p1 == len(p):
return True
else:
return False
4. 总结
难度medium。
