c********p
发帖数: 1969 | 1 有人总结过没？
是不是只有leetcode上那2道题？
这种题我一遇到就不知道从何下手，谁有什么秘诀么！？ |
s*******s
发帖数: 1031 | 2 对:
S = s1s2.....sj.........sn
P = p1p2p3....pi-1pi...pm
M[i][j] 是p1p2...pi match s1s2...sj的情况。
由 p1p2...pi-1 match s1s2...sj-1 以及p1p2...pi-1 match s1s2...sj的情况推出。
最后返回M[m][n]就行了。
【在 c********p 的大作中提到】
: 有人总结过没？
: 是不是只有leetcode上那2道题？
: 这种题我一遇到就不知道从何下手，谁有什么秘诀么！？
|
J****3
发帖数: 427 | |
c********p
发帖数: 1969 | 4 那个题看了答案我知道怎么做，可是题会变。。。
有没有多一些的题，我多做做找找感脚？
。
【在 s*******s 的大作中提到】
: 对:
: S = s1s2.....sj.........sn
: P = p1p2p3....pi-1pi...pm
: M[i][j] 是p1p2...pi match s1s2...sj的情况。
: 由 p1p2...pi-1 match s1s2...sj-1 以及p1p2...pi-1 match s1s2...sj的情况推出。
: 最后返回M[m][n]就行了。
|
c********p
发帖数: 1969 | 5 一个是＊， 还一个是 . *
【在 J****3 的大作中提到】
: *. 的题吗
|
r**h
发帖数: 1288 | 6 正则表达式（不是wildcard）的标准解法，是递归还是DP呢
。
【在 s*******s 的大作中提到】
: 对:
: S = s1s2.....sj.........sn
: P = p1p2p3....pi-1pi...pm
: M[i][j] 是p1p2...pi match s1s2...sj的情况。
: 由 p1p2...pi-1 match s1s2...sj-1 以及p1p2...pi-1 match s1s2...sj的情况推出。
: 最后返回M[m][n]就行了。
|
c******a
发帖数: 789 | 7 DP优于递归，考虑到递归calculate the same things over and over again.
也可以递归＋memorize，跟dp就一个道理了。
我要是面试官，我两种都接受。前提是你能说清楚哪个好，为啥，怎么优化。
【在 r**h 的大作中提到】
: 正则表达式（不是wildcard）的标准解法，是递归还是DP呢
:
: 。
|
r**h
发帖数: 1288 | 8 从来没想过DP的解法，待会儿试试看~
递归+memorize的原理是什么呢？递归的时候带上一个表示状态的二维矩阵，查询子问
题的时候先查询解有没有被计算过？
【在 c******a 的大作中提到】
: DP优于递归，考虑到递归calculate the same things over and over again.
: 也可以递归＋memorize，跟dp就一个道理了。
: 我要是面试官，我两种都接受。前提是你能说清楚哪个好，为啥，怎么优化。
|
J****3
发帖数: 427 | 9 就是减枝吗？ memorze之前已经递过的结果
【在 r**h 的大作中提到】
: 从来没想过DP的解法，待会儿试试看~
: 递归+memorize的原理是什么呢？递归的时候带上一个表示状态的二维矩阵，查询子问
: 题的时候先查询解有没有被计算过？
|
c******a
发帖数: 789 | 10 带一个，查到就返回。没查到就算算，一算好就放进去。
【在 r**h 的大作中提到】
: 从来没想过DP的解法，待会儿试试看~
: 递归+memorize的原理是什么呢？递归的时候带上一个表示状态的二维矩阵，查询子问
: 题的时候先查询解有没有被计算过？
|
|
|
r**h
发帖数: 1288 | 11 这我有点不理解了
要暂存的是不是应该是s的某一个子串和p的某一个子串的匹配结果呢？如果是的话是需
要两个string吗？
如果不是的话，这里的string是什么呢？
【在 c******a 的大作中提到】
: 带一个，查到就返回。没查到就算算，一算好就放进去。
|
c******a
发帖数: 789 | 12 就是这个意思，sorry手快人笨。
你想DP的话，行代表regex的substring，列代表target string的substring，然后右拐
下拐走啊走，实质上就是纪录, boolean>
【在 r**h 的大作中提到】
: 这我有点不理解了
: 要暂存的是不是应该是s的某一个子串和p的某一个子串的匹配结果呢？如果是的话是需
: 要两个string吗？
: 如果不是的话，这里的string是什么呢？
|
c********p
发帖数: 1969 | 13 你们讨论的太高深了，我都晕了。。。。
【在 r**h 的大作中提到】
: 这我有点不理解了
: 要暂存的是不是应该是s的某一个子串和p的某一个子串的匹配结果呢？如果是的话是需
: 要两个string吗？
: 如果不是的话，这里的string是什么呢？
|
r**h
发帖数: 1288 | 14 谢谢指点！待会儿写一个试试看
记得有看到说有人面F，写了个递归，人家问他怎么优化的，这会儿正纳闷呢:)
本来这会儿有个面试，结果对方临时有事推迟了，郁闷啊
【在 c******a 的大作中提到】
: 就是这个意思，sorry手快人笨。
: 你想DP的话，行代表regex的substring，列代表target string的substring，然后右拐
: 下拐走啊走，实质上就是纪录, boolean>
|
c********p
发帖数: 1969 | 15 别郁闷，是你的，跑不掉的。
【在 r**h 的大作中提到】
: 谢谢指点！待会儿写一个试试看
: 记得有看到说有人面F，写了个递归，人家问他怎么优化的，这会儿正纳闷呢:)
: 本来这会儿有个面试，结果对方临时有事推迟了，郁闷啊
|
w******j
发帖数: 185 | 16 差不多吧，
就是
*, +, ?, ^, $, . |
c********p
发帖数: 1969 | 17 然后随机组合？
【在 w******j 的大作中提到】
: 差不多吧，
: 就是
: *, +, ?, ^, $, .
|
w******j
发帖数: 185 | 18 也不是吧，
一般有两种，
一个regex match
这个一般是，./* or ./+ or ./+/*
比较少见的是加上^/$
然后是wildcard matching
这个就是*/? 或者只有* 吧.... |
c********p
发帖数: 1969 | 19 阿，这样阿。。。
我一点都不懂，你点播了一下，我就可以自己去查咯～
谢谢你哦！
【在 w******j 的大作中提到】
: 也不是吧，
: 一般有两种，
: 一个regex match
: 这个一般是，./* or ./+ or ./+/*
: 比较少见的是加上^/$
: 然后是wildcard matching
: 这个就是*/? 或者只有* 吧....
|
z****e
发帖数: 54598 | 20 我依稀记得，string的hashcode会出现最糟糕的情况
也就是搜索的效率会变成全部用equals去判断的情况
这种极端恶劣的前提下，dp反而还不如用递归
【在 c******a 的大作中提到】
: 带一个，查到就返回。没查到就算算，一算好就放进去。
|
g**G
发帖数: 767 | 21 字符串的题，可以画矩阵找思路
比如最长公共子序列，正则匹配，编辑距离……等等 |
g**G
发帖数: 767 | 22 这个题对于我来说递归难于DP ，边边角角的case太多……
【在 r**h 的大作中提到】
: 谢谢指点！待会儿写一个试试看
: 记得有看到说有人面F，写了个递归，人家问他怎么优化的，这会儿正纳闷呢:)
: 本来这会儿有个面试，结果对方临时有事推迟了，郁闷啊
|
