leetcode代码200题c++

class Solution { public: struct node { bool is; node *next[26]; }; vector<string>res; vector<vector<char>>board; node *root; set<string> st; int row; int col; void buildtrie(string s) { node *head=root; int len=s.length(); for(int i=0;i<len;i++) { if(head->next[s[i]-'a']==NULL) { node *p=(node*)malloc(sizeof(node)); p->is=false; for(int i=0;i<26;i++) p->next[i]=NULL; head->next[s[i]-'a']=p; } head=head->next[s[i]-'a']; } head->is=true; } bool find(string s) { int len=s.length(); if(len==0) return false; node *ptr=root; int i=0; while(i<len&&ptr->next[s[i]-'a']) { ptr=ptr->next[s[i]-'a']; i++; } if(i==len&&ptr!=NULL&&ptr->is==true) return true; return false; } bool isprefix(string s) { int len=s.length(); if(len==0) return true; node *ptr=root; int i=0; while(i<len&&ptr->next[s[i]-'a']) { ptr=ptr->next[s[i]-'a']; i++; if(ptr==NULL) break; } if(i==len) return true; return false; } void dfs(vector<vector<bool>> visit,string s,int x,int y) { int k[]={-1,0,1,0}; int l[]={0,-1,0,1}; visit[x][y]=true; if(isprefix(s)) { for(int i=0;i<4;i++) { int xx=x+k[i]; int yy=y+l[i]; if(xx>=0&&xx<row&&yy>=0&&yy<col&&visit[xx][yy]==false) { s.push_back(board[xx][yy]); if(find(s)) st.insert(s); if(isprefix(s)) dfs(visit,s,xx,yy); s.pop_back(); } } } } vector<string> findWords(vector<vector<char>>& board1, vector<string>& words) { board=board1; root=(node*)malloc(sizeof(node)); root->is=false; for(int i=0;i<26;i++) root->next[i]=NULL; for(int i=0;i<words.size();i++) buildtrie(words[i]); row=board.size(); col=board[0].size(); vector<vector<bool>> visit(row,vector<bool>(col,false)); string s=""; for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { s.push_back(board[i][j]); if(find(s)) st.insert(s); if(isprefix(s)) dfs(visit,s,i,j); s.pop_back(); } } set<string>::iterator it; for( it=st.begin();it!=st.end();it++) res.push_back(*it); return res; } }; class Solution { public: struct node { bool is; node *next[26]; }; vector<string>res; vector<vector<char>>board; node *root; set<string> st; int row; int col; void buildtrie(string s) { node *head=root; int len=s.length(); for(int i=0;i<len;i++) { if(head->next[s[i]-'a']==NULL) { node *p=(node*)malloc(sizeof(node)); p->is=false; for(int i=0;i<26;i++) p->next[i]=NULL; head->next[s[i]-'a']=p; } head=head->next[s[i]-'a']; } head->is=true; } bool find(string s) { int len=s.length(); if(len==0) return false; node *ptr=root; int i=0; while(i<len&&ptr->next[s[i]-'a']) { ptr=ptr->next[s[i]-'a']; i++; } if(i==len&&ptr!=NULL&&ptr->is==true) return true; return false; } bool isprefix(string s) { int len=s.length(); if(len==0) return true; node *ptr=root; int i=0; while(i<len&&ptr->next[s[i]-'a']) { ptr=ptr->next[s[i]-'a']; i++; if(ptr==NULL) break; } if(i==len) return true; return false; } void dfs(vector<vector<bool>> visit,string s,int x,int y) { int k[]={-1,0,1,0}; int l[]={0,-1,0,1}; visit[x][y]=true; if(isprefix(s)) { for(int i=0;i<4;i++) { int xx=x+k[i]; int yy=y+l[i]; if(xx>=0&&xx<row&&yy>=0&&yy<col&&visit[xx][yy]==false) { string tt=s+board[xx][yy]; //s.push_back(board[xx][yy]); if(find(tt)) st.insert(tt); if(isprefix(tt)) dfs(visit,s+board[xx][yy],xx,yy); } } } } vector<string> findWords(vector<vector<char>>& board1, vector<string>& words) { board=board1; root=(node*)malloc(sizeof(node)); root->is=false; for(int i=0;i<26;i++) root->next[i]=NULL; for(int i=0;i<words.size();i++) buildtrie(words[i]); row=board.size(); col=board[0].size(); vector<vector<bool>> visit(row,vector<bool>(col,false)); string s=""; for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { s.push_back(board[i][j]); if(find(s)) st.insert(s); if(isprefix(s)) dfs(visit,s,i,j); s.pop_back(); } } set<string>::iterator it; for( it=st.begin();it!=st.end();it++) res.push_back(*it); return res; } };