Why I got an Output Limits Extend for my code?


  • 0
    P
    class Solution {
    private:
    const static int dict_sz = 'z' - 'a' + 1;
    const int xd[4] = {-1, 0, 1, 0};
    const int yd[4] = {0, -1, 0, 1};
    struct Trie{
        vector<vector<int> > ch;
        vector<int> val;
        Trie(){
            vector<int> v;
            v.resize(dict_sz);
            int i;
            for(i=0;i<dict_sz;i++)v[i]=0;
            ch.push_back(v);
            val.push_back(0);
        }
        
        void insert(string str){
            int len = str.length(),i,v=0;
            for(i=0;i<len;i++){
                int c = idx(str[i]);
                if(!ch[v][c]){
                    val.push_back(0);
                    vector<int>vec;
                    vec.resize(dict_sz);
                    int j;
                    for(j=0;j<dict_sz;j++)vec[j]=0;
                    ch.push_back(vec);
                    ch[v][c] = ch.size() - 1;
                }
                v = ch[v][c];
            }
            val[v] = 1;
        }
        int idx(char c){return c - 'a';}
    };
    
    int idx(char c){return c - 'a';}
    
    public:
        vector<string> findWords(vector<vector<char> >& board, vector<string>& words) {
            int n = board.size();
            vector<string> ret;
            if(n<=0)return ret;
            int m = board[0].size();
            if(m <= 0 )return ret;
            Trie trie;
            int i,j;
            for(i=0;i<words.size();i++)trie.insert(words[i]);
            int hash[n*m];
            memset(hash,0,sizeof(hash));
            for(i=0;i<n;i++)
                for(j=0;j<m;j++){
                    int v = 0;
                    vector<char> path;
                    dfs(i,j,board,trie,ret,hash,path,v);
                }
            return ret;
        }
        
        void dfs(int i, int j,vector<vector<char> >&board, Trie& trie, vector<string>& ret,int* hash, vector<char>& path, int v){
            int n = board.size(),m = board[0].size();
            if(i>=0&&i<n&&j>=0&&j<m&&!hash[i*m+j]&&(v=trie.ch[v][idx(board[i][j])])){
                hash[i*m +j] = 1;
                path.push_back(board[i][j]);
                if(trie.val[v]){
                    string tmp;
                    tmp.resize(path.size());
                    int k;
                    for(k=0;k<path.size();k++)tmp[k]=path[k];
                    bool contained = false;
                    int q;
                    for(q=0;q<ret.size();q++)if(tmp.compare(ret[q]) == 0){contained = true;break;}
                    if(!contained)ret.push_back(tmp);
                }
                int p;
                for(p=0;p<4;p++)dfs(i+xd[p],j+yd[p],board,trie,ret,hash, path,v);
                hash[i*m+j] = 0;
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.