y*******d
发帖数: 1674 | 1 1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*':
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]
//in this case, a* only counts as empty
2 if p.charAt(j-1) == s.charAt(i) or p.charAt(j-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a*
counts as multiple a
or dp[i][j] = dp[i][j-1] // in this case, a*
counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a*
counts as empty
Dont understand why the following: any examples? thanks.
dp[i][j] = dp[i-1][j] //in this case, a*
counts as multiple a | s******n
发帖数: 240 | 2 i表示的是在s里的字符位置，j表示在pattern里的字符位置
dp[i][j] = dp[i-1][j]的意思是，pattern匹配到j不变的情况下，s里多向前移动一个
字符。任何s有重复字符与p匹配的情况都是例子。
s = "aaaa"
p = "a*"
dp[4][2] = dp[3][2] = dp[2][2] = dp[1][2] | y*******d
发帖数: 1674 | 3 谢谢
【在 s******n 的大作中提到】
: i表示的是在s里的字符位置，j表示在pattern里的字符位置
: dp[i][j] = dp[i-1][j]的意思是，pattern匹配到j不变的情况下，s里多向前移动一个
: 字符。任何s有重复字符与p匹配的情况都是例子。
: s = "aaaa"
: p = "a*"
: dp[4][2] = dp[3][2] = dp[2][2] = dp[1][2]
|
|
