p*****3 发帖数: 488 | 1 //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
}
else i += 1;
}
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2;)
{
if (pattern[j] != '*' && pattern[j] != '+')
{
DP[i][j] = (((str[i-1] == pattern[j-1]) || pattern[j-1] == '
.') && DP[i-1][j-1]);
j++;
}
else
{
int iter = i;
if (pattern[j] == '+')
{
if (pattern[j-1] != '.' && pattern[j-1] != str[i-1])
{
j += 2;
continue;
}
else iter--;
}
do
{
if (DP[iter][j-1])
{
DP[i][j] = true;
DP[i][j+1] = true;
break;
}
}
while (iter > 0 && str[iter-- - 1] == pattern[j-1]);
j += 2;
}
}
}
return DP[len1][len2];
}
============================
以前一直觉得很难,发现也不是太难写 |
x*****0 发帖数: 452 | |
h**i 发帖数: 431 | 3 顶id。。。。
【在 p*****3 的大作中提到】 : //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false : const int M = 100; : bool isMatchDP(const char* str, const char* pattern) : { : if (NULL == str || NULL == pattern) : return false; : int len1 = strlen(str); : int len2 = strlen(pattern); : bool DP[M][M] = { false }; //DP[len1+1][len2+1] : DP[0][0] = true;
|
h*******0 发帖数: 270 | |
c********p 发帖数: 1969 | |
J****3 发帖数: 427 | |
h***u 发帖数: 9 | |
p*****3 发帖数: 488 | 8
真有眼光,
头像是精心挑选的!
【在 J****3 的大作中提到】 : 顶!头像也很稀饭!
|
e*****n 发帖数: 316 | |
j********x 发帖数: 2330 | |
|
|
k*j 发帖数: 153 | 11 贴一个从后往前的DPcode。与lz的解法大同小异
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len1 = strlen(s);
int len2 = strlen(p);
int i,j;
vector > result(len1+1,vector (len2+1,0));
result[len1][len2] = 1;
for(j = len2-1;j>=0;j--){
if(*(p+j+1)=='*'){
result[len1][j] = result[len1][j+2];
}
}
for(i = len1-1;i>=0;i--){
for(j = len2-1;j>=0;j--){
if(*(p+j)=='.'){
if(*(p+j+1)=='*'){
result[i][j] = result[i+1][j];
if(!result[i][j] && j+2<=len2)
result[i][j] = result[i][j+2];
}
else
result[i][j] = result[i+1][j+1];
}
else if(*(p+j)=='*')
result[i][j] = 0;
else{
if(*(p+j)=='*')
result[i][j] = result[i][j+2] || *(p+j)==*(s+i) && result[
i+1][j];
else
result[i][j] = *(p+j)==*(s+i) && result[i+1][j+1];
}
}
}
return result[0][0];
}
}; |
d****n 发帖数: 233 | 12 Just curious, what if there is '*' in the s, does it still work?
【在 k*j 的大作中提到】 : 贴一个从后往前的DPcode。与lz的解法大同小异 : class Solution { : public: : bool isMatch(const char *s, const char *p) { : // Start typing your C/C++ solution below : // DO NOT write int main() function : : int len1 = strlen(s); : int len2 = strlen(p); : int i,j;
|
d****n 发帖数: 233 | 13 public class Solution {
public boolean isMatch(String s, String p) {
if (p=="") return s == "";
int m = s.length() + 1;
int n = p.length() + 1;
boolean[][] result = new boolean[n][m];
// Initialization part
result[0][0] = true;
result[1][0] = false;
for( int i = 2; i < n; i++)
result[i][0] = p.charAt(i-1) == '*' ? result[i-2][0] : false;
for( int j = 1; j < m; j++){
result[0][j] = false;
result[1][j] = false;
}
if (m > 1)
result[1][1] = match(s.charAt(0), p.charAt(0));
// Major DP part
for( int i = 2; i < n; i++ ){
for( int j = 1; j < m; j++ ){
if(p.charAt(i-1) == '*')
result[i][j] = match(s.charAt(j-1),p.charAt(i-2))?
(result[i][j-1]||result[i-2][j]) : result[i-2][j];
else
result[i][j] = match(s.charAt(j-1),p.charAt(i-1))?
result[i-1][j-1] : false;
}
}
return result[n-1][m-1];
}
boolean match(char a, char b){
return (a == b || b=='.');
}
} |
d****n 发帖数: 233 | 14 Another one for Wildcard match:
public class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1;
int n = p.length() + 1;
boolean[][] result = new boolean[n][m];
result[0][0] = true;
for( int i = 1; i < n; i++){
result[i][0] = p.charAt(i-1) == '*' ? result[i-1][0] : false;
}
for( int j = 1; j < m; j++){
result[0][j] = false;
}
for( int i = 1; i < n; i++ ){
for( int j = 1; j < m; j++ ){
if(p.charAt(i-1) == '*'){
result[i][j] = result[i-1][j]|result[i-1][j-1]|result[i][j-1];
} else
result[i][j] = match(s.charAt(j-1),p.charAt(i-1)) ?
result[i-1][j-1] : false;
}
}
return result[n-1][m-1];
}
boolean match(char a, char b){
return (a == b || b=='?');
}
}
【在 d****n 的大作中提到】 : public class Solution { : public boolean isMatch(String s, String p) { : if (p=="") return s == ""; : : int m = s.length() + 1; : int n = p.length() + 1; : boolean[][] result = new boolean[n][m]; : : // Initialization part : result[0][0] = true;
|
c******o 发帖数: 534 | 15 顶,晚上来学习
★ 发自iPhone App: ChineseWeb 7.8
【在 p*****3 的大作中提到】 : //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false : const int M = 100; : bool isMatchDP(const char* str, const char* pattern) : { : if (NULL == str || NULL == pattern) : return false; : int len1 = strlen(str); : int len2 = strlen(pattern); : bool DP[M][M] = { false }; //DP[len1+1][len2+1] : DP[0][0] = true;
|