c********p
发帖数: 1969 | |
c********p
发帖数: 1969 | 2 上代码，大家批斗！
public class Solution {
public boolean isMatch(String s, String p) {
// Start typing your Java solution below
// DO NOT write main() function
if(s == null || p == null){
return false;
}
int slen = s.length();
int plen = p.length();
boolean[][] dp = new boolean[slen + 1][plen + 1];
dp[0][0] = true;
for(int i = 1; i <= plen; i++){
if(p.charAt(i - 1) == '*'){
if( dp[0][i - 1]== true){
dp[0][i] = true;
}
}
}
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= p.length(); j++){
if((p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j
- 1)) && dp[i - 1][j - 1] == true){
dp[i][j] = true;
}else if(p.charAt(j - 1) == '*'){
for(int k = 0; k < i; k++){
if(dp[k][j - 1] == true){
dp[i][j] = true;
break;
}
if(dp[i][j - 1] == true){
dp[i][j] = true;
}
}
}
}
}
return dp[slen][plen];
}
}
【在 c********p 的大作中提到】
: 求帮助
|
p*****3
发帖数: 488 | 3
我觉得你好牛，这题用dp不容易，膜拜一下
【在 c********p 的大作中提到】
: 求帮助
|
p*****2
发帖数: 21240 | |
p*****3
发帖数: 488 | 5
确定不是O(1)?
【在 p*****2 的大作中提到】
: dp过不了吧？要O(n)才行
|
c********p
发帖数: 1969 | 6 就是过不了啊，才问你怎么办啊！
【在 p*****2 的大作中提到】
: dp过不了吧？要O(n)才行
|
p*****2
发帖数: 21240 | 7
不用办。这样就可以了。
【在 c********p 的大作中提到】
: 就是过不了啊，才问你怎么办啊！
|
c********p
发帖数: 1969 | 8 怎么O(n)?
我的确实过不了大oj，我的n^2
【在 p*****2 的大作中提到】
:
: 不用办。这样就可以了。
|
c********p
发帖数: 1969 | 9 你怎么做的这个题？
怎么过的大oj？
【在 p*****3 的大作中提到】
:
: 确定不是O(1)?
|
p*****2
发帖数: 21240 | 10
我感觉不用追求O(n), 面试dp就可以了
【在 c********p 的大作中提到】
: 怎么O(n)?
: 我的确实过不了大oj，我的n^2
|
|
|
c********p
发帖数: 1969 | 11 告诉偶，好么。。。。
献上一束花～
【在 p*****2 的大作中提到】
:
: 我感觉不用追求O(n), 面试dp就可以了
|
c********p
发帖数: 1969 | 12 是说滚动数组么？
【在 p*****2 的大作中提到】
:
: 我感觉不用追求O(n), 面试dp就可以了
|
p*****2
发帖数: 21240 | 13
greedy
【在 c********p 的大作中提到】
: 告诉偶，好么。。。。
: 献上一束花～
|
i********s
发帖数: 22 | 14 这个题目比较恶心，O（N*N）超内存，直接DP超时。
我在DP基础上做了一个长度剪枝，通过大数据，感觉是OJ上有些比较tricky的case；
附上我的解答；
https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
wildcardmatch2.cpp |
g**G
发帖数: 767 | 15 这种问题用二维数组确实太浪费空间了，不是一种好做法
设想你匹配一个1M的文件和一个100个char的pattern，光数组就要开100M ，但其中只
有一条路线是标记了的，其他空间的都浪费了 |
f*******b
发帖数: 520 | 16 这题是要上DP的，LZ用的方法和我开始一样，但通过不了大数据，不是DP的问题，是所
用算法本身的问题，我改了后就能过大数据了：
public boolean isMatch(String s, String p) {
int count=0;
for(int i=0;i
if(p.charAt(i)!='*') count++;
if(count>s.length()) return false;
if(s.length()==0) return true;
if(p.length()==0) return s.length()==0;
boolean[][] blc=new boolean[s.length()+1][p.length()+1];
blc[0][0]=true;
for(int j=1;j
for(int i=1;i
if(p.charAt(j-1)=='*'){
if(blc[i-1][j-1]==true){
for(int m=i-1;m<=s.length();m++) blc[m][j]=true;
break;
}
if(blc[i][j-1]==true){
for(int m=i;m<=s.length();m++) blc[m][j]=true;
break;
}
}
else{
if((p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='?')&&
blc[i-1][j-1]==true) blc[i][j]=true;
}
}
}
return blc[s.length()][p.length()];
} |
r**d
发帖数: 316 | 17 如果按列dp的话，不用保存整个二维数组，只要保存两个一维数组即可，一个是当前列
，一个是前一列。
【在 i********s 的大作中提到】
: 这个题目比较恶心，O（N*N）超内存，直接DP超时。
: 我在DP基础上做了一个长度剪枝，通过大数据，感觉是OJ上有些比较tricky的case；
: 附上我的解答；
: https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
: wildcardmatch2.cpp
|
s*******s
发帖数: 1031 | 18 我的C++代码：
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int ptnCnt = 0;
const char *pp = p;
while(pp && (*pp)) {
if(*pp != '*')
++ptnCnt;
++pp;
}
int strCnt = 0;
if(s)
strCnt = strlen(s);
if(strCnt < ptnCnt)
return false;
if(!strCnt)
return !ptnCnt;
if(!ptnCnt)
return strlen(p);
int n = strCnt;
vector > M(2, vector(n+1, false));
M[0][0] = true;
int flag = 1;
pp = p;
while(pp && *pp) {
if(*pp == '*') {
int i = 0;
while(i<=n && !M[!flag][i]) {
M[flag][i] = false;
++i;
}
while(i<=n) {
M[flag][i] = true;
++i;
}
} else {
M[flag][0] = false;
for(int i=1; i<=n; ++i) {
if(*pp=='?' || *pp==s[i-1])
M[flag][i] = M[!flag][i-1];
else
M[flag][i] = false;
}
}
flag = !flag;
++pp;
}
return M[!flag][n];
}
};
【在 c********p 的大作中提到】
: 上代码，大家批斗！
: public class Solution {
: public boolean isMatch(String s, String p) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if(s == null || p == null){
: return false;
: }
:
: int slen = s.length();
|
c********p
发帖数: 1969 | |
c********p
发帖数: 1969 | 20 我刚看了一下你的代码，没太看懂为什么这样做。
根据p 的长度，得出是一行还是2行，可是为啥这么做？是不是也相当于是滚动数组呢？
【在 i********s 的大作中提到】
: 这个题目比较恶心，O（N*N）超内存，直接DP超时。
: 我在DP基础上做了一个长度剪枝，通过大数据，感觉是OJ上有些比较tricky的case；
: 附上我的解答；
: https://github.com/xiongjunliang/leetcode/blob/master/wildcardmatch/
: wildcardmatch2.cpp
|
|
|
c********p
发帖数: 1969 | 21 其实，也就是说，只差在一个地方，就是在最最开始，要count一下非＊的字符个数，
比较s的长度。
只有这个地方有问题，是吧？
【在 f*******b 的大作中提到】
: 这题是要上DP的，LZ用的方法和我开始一样，但通过不了大数据，不是DP的问题，是所
: 用算法本身的问题，我改了后就能过大数据了：
: public boolean isMatch(String s, String p) {
: int count=0;
: for(int i=0;i: if(p.charAt(i)!='*') count++;
: if(count>s.length()) return false;
: if(s.length()==0) return true;
: if(p.length()==0) return s.length()==0;
: boolean[][] blc=new boolean[s.length()+1][p.length()+1];
|
c********p
发帖数: 1969 | 22 滚动数组，是么？
【在 r**d 的大作中提到】
: 如果按列dp的话，不用保存整个二维数组，只要保存两个一维数组即可，一个是当前列
: ，一个是前一列。
|
r**d
发帖数: 316 | 23 是的
【在 c********p 的大作中提到】
: 滚动数组，是么？
|
