Runtime Error : Last executed input: "a", []


  • 0
    S

    Every word is a valid dictionary word, but why can it input "a", []?

    struct Node {
    int index;
    int pos;
    int v;
    Node(int a = -1, int b = -1, int c = -1) : index(a), pos(b), v(c) {}
    bool operator < (const Node &p) const {
    return index < p.index;
    }
    };

    const int N = 1000010;

    class Solution {
    public:
    int trie[N][26];
    int cnt;
    vector<string> str;
    vector<string> comb;
    int vis[N];
    vector<Node> G[10010];
    Node path[N];
    int *travel;
    queue<Node> pque;
    int Clength;

    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        comb.clear();
    	if(dict.size() <= 0)
    		return comb;
        init(s.size() + 1);
        construct(dict);
        procede(s);
        cnt = 0;
        dfs(0);
        return comb;
    }
    
    void construct(unordered_set<string> &dict) {
        for(const auto &ptr : dict) {
            str.push_back(ptr);
        }
        
        int len = str.size();
        for(int i = 0; i < len; ++ i) {
            string &p = str[i];
            int u = 0, pre = 0;
            //cout << p << endl;
            for(int j = 0; p[j]; ++ j) {
            	int ch = p[j] - 'a';
                if(!trie[u][ch]) {
                	memset(trie[cnt], 0, sizeof(trie[cnt]));
                	trie[u][ch] = cnt ++;
                }
                pre = u;
                u = trie[u][ch];
            }
            vis[pre] = i;
        }
    
        /*for(int i = 0; i < cnt; ++ i) {
        	for(int j = 0; j < 20; ++ j)
        		cout << trie[i][j] << " ";
        	cout << endl;
        }*/
        /*for(int i = 0; i < 20; ++ i)
        	cout << i << " ";
        cout << endl;
        for(int i = 0; i < 18; ++ i)
        	cout << vis[i] << " ";
        cout << endl;
        cout << cnt << endl;*/
    }
    
    void init(const int len) {
    	while(!pque.empty())
    		pque.pop();
    	travel = new int[len];
    	for(int i = 0; i < len; ++ i)
    		travel[i] = -1;
        for(int i = 0; i < N; ++ i)
            vis[i] = -1;
    	G[0].clear();
        str.clear();
        comb.clear();
        cnt = 1;
        memset(trie[0], 0, sizeof(trie[0]));
        Clength = len - 1;
    }
    
    void procede(string &s) {
    	cnt = 1;
    	pque.push({0, -1, 0});
    	while(!pque.empty()) {
    		Node p = pque.front();
    		pque.pop();
    		int u = 0;
    		int i = p.index;
    		//cout << "i = " << i << endl;
    		for( ; ; ++ i) {
    			int ch = s[i] - 'a';
    			if(!s[i] || trie[u][ch]) {
    				//cout << u << endl;
    				if(vis[u] != -1) {
    					/*cout << p.v << " " << i << " " << ch << " " << u << endl;
    					cout << s[i] << " " << vis[u] << endl;*/
    					if(travel[i] == -1) {
    						travel[i] = cnt;
    						pque.push({i + 1, vis[u], cnt});
    					}
    					G[p.v].push_back({i + 1, vis[u], travel[i]});
    					G[cnt ++].clear();
    				}
    				if(!s[i]) {
    					//cout << "i = " << i << "  u = " << u << endl;
    					break;
    				}
    			}
    			else {
    				//cout << "i = " << i << "  u = " << u << endl;
    				break;
    			}
    			u = trie[u][ch];
    		}
    	}
    	/*cout << cnt << endl;
    	for(int i = 0; i < cnt; ++ i) {
    		int length = G[i].size();
    		cout << "length = " << length << endl;
    		for(int j = 0; j < length; ++ j) {
    			cout << "index = " << G[i][j].index << "  pos = " << G[i][j].pos << "  v = " << G[i][j].v << endl;
    		}
    	}*/
    }
    
    void dfs(int u) {
    	int len = G[u].size();
    	for(int i = 0; i < len; ++ i) {
    		Node &p = G[u][i];
    		path[cnt ++] = p;
    		if(p.index != Clength)
    			dfs(p.v);
    		else {
    			string tmp = "";
    			for(int j = 0; j < cnt; ++ j) {
    				tmp += str[path[j].pos];
    				if(j != cnt - 1)
    					tmp += " ";
    			}
    			comb.push_back(tmp);
    		}
    		-- cnt;
    	}
    }
    

    };


Log in to reply
 

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