I thought the problem missed some legit solutions...


  • -3
    R

    My solution gives four solution sets for the original problem:

     hit hot dot dog cog
     hit hot dot lot log cog
     hit hot lot log cog
     hit hot lot dot dog cog
    

    And I guess they are all valid solutions, even if some are longer?

    The code below:

    bool isIntermediate (string &a, string &b) {
        if (a.length() != b.length() || a.length() == 0) return false;
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a[i] != b[i]) diff++;
        }
        return diff == 1;
    }
    
    bool find(string &start, string &end, vector<vector<string> > &result, 
            vector<string> &path, unordered_set<string> &dict) {
        if (isIntermediate(start, end) ) {
            path.push_back(end);
            result.push_back(path);
            path.pop_back();
            return true;
        }
        for (auto word : dict) {
            if (isIntermediate(start, word) ) {
                path.push_back(word);
                unordered_set<string> tempDict = dict;
                tempDict.erase(word);
                find(word, end, result, path, tempDict);
                path.pop_back();
            }
        }
        return false;
    }
    
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
        vector<vector<string> > result;
        vector<string> path;
        path.push_back(start);
        find (start, end, result, path, dict);
        return result;
    }

  • 0

    From the problem statement:

    find all shortest transformation sequence(s)


Log in to reply
 

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