void dfs(vector<vector<char> >&vec,int i,int j){
if(vec[i][j]=='O'){
vec[i][j]='Y';
if(i > 0) dfs(vec,i1,j);
if(j > 1) dfs(vec,i,j1); //here it is supposed to be j > 0, however it brings me runtime error if I do that
if(i+1 < m) dfs(vec,i+1,j);
if(j+1 < n) dfs(vec,i,j+1);
}
}
yingying.chen.7370
@yingying.chen.7370
Posts made by yingying.chen.7370

Simple Code, wired error, anyone can help?

O(k) space 6 lines C++
vector<int> getRow(int rowIndex) { vector<int> res; for (int i = 0; i <= rowIndex; i++){ res.push_back(1); for (int j = i1; j >= 1; j) res[j] += res[j1]; } return res; }

RE: My C++ solution with one pass and O(n) time and O(n) space
your solution is O(1) space, not O(n)

O(n) time, O(1) space C++ 16 ms solution, no tricks, no recursion[explained]
the idea is very simple, keep finding the earliest possible match for every part of p that doesn't contain any '*' in s, if they all match then it is pretty much true, otherwise not.
class Solution { public: bool isMatch(string s, string p){ if (p.size() == 0) return s.size()==0; int laststar = 1; int start = 0; int len = 0; p.push_back('*'); for (int i = 0; i < p.size(); i++){ if (p[i] == '*'){ len = i1laststar; int index = strStr(s, p.substr(laststar+1, len), start); if (index == 1) return false; //if there is a part that can't match // if there is no '*' before the first part in p, and it doesn't match as index == 0 in s if (laststar == 1 && index != 0) return false; start = index+len; //I didn't simplified the code here, I am sure it can be cleaner if (i != p.size()  1) laststar = i; while (i < p.size()  1 && p[i + 1] == '*') i++; if (i != p.size()1) laststar = i; } } p.pop_back(); if (p.back() =='*') return true; if (start == s.size()) return true; if (laststar != 1) { int index = strStr(s, p.substr(p.size()len), s.size()len); if (index == s.size()len) return true; } return false; } int strStr(string& haystack, string needle, int index) { if (needle.size() == 0) return 0; if (haystack.size()==0) return 1; int last = haystack.size()needle.size()+1; int len = needle.size(); for (int i = index; i < last; i++){ int k = 0; while (k < needle.size() && (needle[k] == haystack[i+k]  needle[k] == '?')) k++; if (k == needle.size()) return i; } return 1; } };

RE: C++ code O(NlogK) in time, O(1) in space, Divide_Conquer
I think the divide and conquer action it self with K nodes is O(klogk), and O(n) to merge two lists. So it will be nklogk

RE: C++ code O(NlogK) in time, O(1) in space, Divide_Conquer
Do you mean O(NKlogK) ? How can you do it in O(nlogK) time when there are NK nodes in total that you need to visit?

RE: 12ms 14lines C++
Hi, is there repeating calculation in this algorithm though?
Such as, "cbcaba":we will first found "c", "b", "c", then at this point, we are going to do recursion for "aba" to find all possible solutions for it ;
then later, we also find "cbc" is palindrome, so we are going to do calculation for "aba" again, but we have already done this beforeis there any way to avoid this repeated calculation?