Why my solution works fine locally but get error answer when submission


  • 0
    Y

    Here is my work which has been accepted once and I changed it for improving performance.
    After improving, it can not pass the test when submission but the test can pass locally.
    Please help point out what is wrong with my solution:

    inline void GeneratePath(int parent, unordered_set<int>* parentMap, vector<vector<string>>& out, vector<int> & path, const char ** wordsArray)
    {
        unordered_set<int>& pv = parentMap[parent];
        if (pv.size() > 0)
        {
            for (unordered_set<int>::iterator it = pv.begin(); it!=pv.end(); it++)
            {
                vector<int> v = path;
                v.push_back(parent);
                GeneratePath(*it, parentMap, out, v, wordsArray);
            }
        }
        else
        {
            path.push_back(parent);
            vector<string> rpath;
            for (int j = path.size() - 1; j >= 0; j--)
                rpath.push_back(wordsArray[path[j]]);
            out.push_back(rpath);
        }
    }
    
    vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList)
    {
        vector<vector<string>> ret;
        int wordCount = wordList.size() + 2;
        const char ** wordsArray = new const char*[wordCount];
        int i=0, start = 0, stop = wordCount - 1;
        wordsArray[i++] = beginWord.data();
        for (unordered_set<string>::iterator it = wordList.begin(); it != wordList.end(); it++)
            wordsArray[i++] = it->data();
        wordsArray[i++] = endWord.data();
    
        int *depthMap = new int[wordCount];
        memset(depthMap, -1, wordCount);
        int l = beginWord.size();
        int shortest = numeric_limits<int>::max();
        unordered_set<int>* parentMap = new unordered_set<int>[wordCount];
        deque<int> nodeQ;
        nodeQ.push_back(start);
        depthMap[start] = 0;
        //broad traverse to find the shortest path
        while (!nodeQ.empty())
        {
            int parent = nodeQ.front();
            nodeQ.pop_front();
            if (depthMap[parent] >= shortest)
                continue;
            int nodeDepth = depthMap[parent] + 1;
            for (int j = 0; j < wordCount; j++)
            {
                int c = 0;
                for (size_t k = 0; k < l; k++)
                    if (c <= 1 && wordsArray[parent][k] != wordsArray[j][k]) c++;
                if (c != 1)
                    continue;
                int node = j;
                if (depthMap[node] > -1 && depthMap[node] <= depthMap[parent])
                    continue;
                if (node == stop)
                {
                    shortest = shortest > nodeDepth ? nodeDepth : shortest;
                    vector<int> path;
                    path.push_back(node);
                    GeneratePath(parent, parentMap, ret, path, wordsArray);
                    break;
                }
                else
                {
                    if (nodeQ.size()==0||nodeQ.end() == find(nodeQ.begin(), nodeQ.end(), node))
                    {
                        nodeQ.push_back(node);
                        depthMap[node] = nodeDepth;
                    }
                    parentMap[node].insert(parent);
                }
            }
        } 
        delete []wordsArray;
        delete []depthMap;
        delete []parentMap;
        for (size_t i = 0; ret.size()>0 && i < ret[0].size(); i++)
        {
            cout << ret[0][i] << " ";
        }
        return ret;
    }
    
    void TestWordLadder()
    {
        //char * s[] = { "hot", "dot", "dog", "lot", "log" };
        //char * s[] = { "ted", "tex", "red", "tax", "tad", "den", "rex", "pee"};
        char * s[] = { "a", "b", "c"};
       // char * s[] = {        "dose", "ends", "dine", "jars", "prow", "soap", "guns", "hops", "cray", "hove", "ella", "hour", "lens", "jive", "wiry", "earl", "mara", "part", "flue", "putt", "rory", "bull", "york", "ruts", "lily", "vamp", "bask", "peer", "boat", "dens", "lyre", "jets", "wide", "rile", "boos", "down", "path", "onyx", "mows", "toke", "soto", "dork", "nape", "mans", "loin", "jots", "male", "sits", "minn", "sale", "pets", "hugo", "woke", "suds", "rugs", "vole", "warp", "mite", "pews", "lips", "pals", "nigh", "sulk", "vice", "clod", "iowa", "gibe", "shad", "carl", "huns", "coot", "sera", "mils", "rose", "orly", "ford", "void", "time", "eloy", "risk", "veep", "reps", "dolt", "hens", "tray", "melt", "rung", "rich", "saga", "lust", "yews", "rode", "many", "cods", "rape", "last", "tile", "nosy", "take", "nope", "toni", "bank", "jock", "jody", "diss", "nips", "bake", "lima", "wore", "kins", "cult", "hart", "wuss", "tale", "sing", "lake", "bogy", "wigs", "kari", "magi", "bass", "pent", "tost", "fops", "bags", "duns", "will", "tart", "drug", "gale", "mold", "disk", "spay", "hows", "naps", "puss", "gina", "kara", "zorn", "boll", "cams", "boas", "rave", "sets", "lego", "hays", "judy", "chap", "live", "bahs", "ohio", "nibs", "cuts", "pups", "data", "kate", "rump", "hews", "mary", "stow", "fang", "bolt", "rues", "mesh", "mice", "rise", "rant", "dune", "jell", "laws", "jove", "bode", "sung", "nils", "vila", "mode", "hued", "cell", "fies", "swat", "wags", "nate", "wist", "honk", "goth", "told", "oise", "wail", "tels", "sore", "hunk", "mate", "luke", "tore", "bond", "bast", "vows", "ripe", "fond", "benz", "firs", "zeds", "wary", "baas", "wins", "pair", "tags", "cost", "woes", "buns", "lend", "bops", "code", "eddy", "siva", "oops", "toed", "bale", "hutu", "jolt", "rife", "darn", "tape", "bold", "cope", "cake", "wisp", "vats", "wave", "hems", "bill", "cord", "pert", "type", "kroc", "ucla", "albs", "yoko", "silt", "pock", "drub", "puny", "fads", "mull", "pray", "mole", "talc", "east", "slay", "jamb", "mill", "dung", "jack", "lynx", "nome", "leos", "lade", "sana", "tike", "cali", "toge", "pled", "mile", "mass", "leon", "sloe", "lube", "kans", "cory", "burs", "race", "toss", "mild", "tops", "maze", "city", "sadr", "bays", "poet", "volt", "laze", "gold", "zuni", "shea", "gags", "fist", "ping", "pope", "cora", "yaks", "cosy", "foci", "plan", "colo", "hume", "yowl", "craw", "pied", "toga", "lobs", "love", "lode", "duds", "bled", "juts", "gabs", "fink", "rock", "pant", "wipe", "pele", "suez", "nina", "ring", "okra", "warm", "lyle", "gape", "bead", "lead", "jane", "oink", "ware", "zibo", "inns", "mope", "hang", "made", "fobs", "gamy", "fort", "peak", "gill", "dino", "dina", "tier" };
    
        unordered_set<string> wordList;
        for (int i = 0; i < sizeof(s) / sizeof(char*); i++)
            wordList.insert(s[i]);
        //findLadders("red", "tax", wordList);
        //findLadders("hit", "cog", wordList);
        findLadders("a", "c", wordList);
        //findLadders("nape", "mild", wordList);
    
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
        //TestMaxSumofSubArray();
        //TestLCS();
        //TestCPPA();
        //OutputConsecutiveSum(15);
        //bool res = isNumber("46.e3");
        TestWordLadder();
    	return 0;
    }

  • 0
    Y

    the issue has been resolved.
    the root cause is that the api memset does not work fine when submission. So that a buffer has not been initialized correctly.


Log in to reply
 

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