本文是写一道理的解决过程。
题目： [Sequence Transformation] In Python
https://www.codeeval.com/open_challenges/130/
简介
0可以表示连续的串”A”，
1可以表示连续的串”A” or 串”B”
给出一序列01组合 和AB组合，判断是否可以匹配。
一上手我的第一印象就是用正则表达式。
https://github.com/asmca/codeeval/blob/master/130/130.old.py
这样的代码非常简单，而且小的CASE都能过，但比较大的就不行了，如
https://raw.githubusercontent.com/asmca/codeeval/master/130/a.test
然后就想着在正则上面下文章：
1. 增加锚点， 加上^,$ 稍有改进，但例子更长时候就不行，甚至会报错，类似于只支持100个RE括号云云。
2. 简化RE，这也是相当痛苦的事情：
把 A+(B+|A+) 简化成 A+(B+|A)
A+A+简化成AA+
(B+|A+)A+简化成 (B+|A)A+
这样下来能省一些时间，但大体上，对于(B+|A+)这个式子本身依然无解， 也就意味着大量的错误回溯存在。
回溯对于正则来讲几乎是致命的。
甚至也想了一个递归的办法，
https://github.com/asmca/codeeval/blob/master/130/old.py.recursive
但递归的较大问题是要重复计算小单元，这几乎是指数级的，而这一问题并不比上面的正则做法好多少。
MIN提醒我用动态规划来做。用矩阵存临时结果来取消回溯的w代价。
https://raw.githubusercontent.com/asmca/codeeval/master/130/min.jpg
于是我接下来的时间就同这个矩阵打交道了。花了几个小时的时间才最终通过提交。
这个是题目的输入示例
https://github.com/asmca/codeeval/blob/master/130/130.in
然后 初稿就出来了
https://github.com/asmca/codeeval/blob/master/130/130.1928.py
这份代码一开始运行了15秒。
把函数ifmatching()优化了return的顺序，结果可以达到13秒。
问题在于这边的for循环，同样需要max to O(m*n*n)的复杂度(实际上约为m*n*logN) 依然难以接受。
提交的服务器上时间限制10s，而且很明显上面的限制资源要比我本地运行的慢得多。
这里，
mtx[i][j]设为1， 表示这个s1[:i+1]能够匹配到s2[:j+1]我尝试去限定i和j的位置， 比如j>=i 和j <len(s2)-len(s1)+i+1
即使如此，时间仍然只能达到11秒左右。
此时的版本
https://github.com/asmca/codeeval/blob/master/130/130.py.2203
这个时候基本上可以达到7s左右。但我还是没有找到问题的关键
像这样的代码仍然大量调用ifmatching()函数，复杂度是到了m*n ， 我比较偷懒用了递归。
调整了递归出口，对于每次调用，先直接判定 mtx[x-1][y-1]如果设置，直接退出。 这样时间就大量的节省了
可以做到2.5s左右能够完成， 但此时提交 服务器端仍然超时失败。
对于这样m*n的复杂度，发现 还是会有大量对于ifmatching()的调用，下面的改动就达到了目的
|
|
row=i+1 for col in range(j+1,y-x+i+2): if not mtx[row][col]: if ifmatching(s1[row],s2[j+1:col+1]): mtx[row][col]=1 markdown(row,col) |
TO
|
|
row=i+1 for col in range(j+1,y-x+i+2): if not mtx[row][col]: if not ifmatching(s1[row],s2[j+1:col+1]): break mtx[row][col]=1 markdown(row,col) |
此时可以理解为，如果mtx[i][j]==0 (j>=i),那么，mtx[i][j+]以后都是0
即如果不能匹配一个字符串，那么这个字符串后新加字母，仍不能匹配。
这样的改变，直接中途跳出for循环，减少了对ifmatching的调用。
能达到0.2s的级别， 提交直接成功
Final Code:
https://github.com/asmca/codeeval/blob/master/130/130.py
| Rev |
Language |
Date |
Status |
Score |
Time, ms |
Memory, bytes |
In ranking |
Ranking Points |
|
|
|
| 14 |
Python 2 |
May 11, 2014 |
Solved |
100 |
917 |
4349952 |
yes |
55.278 |
当然，就算这样修改后的循环代码，也没有这样的效率，仍然在9s左右徘徊。
https://github.com/asmca/codeeval/blob/master/130/130.2311.py