leetcode 126. Word Ladder II

ゝ一世哀愁。 2022-08-21 02:19 233阅读 0赞

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return 

  1. [
  2.     ["hit","hot","dot","dog","cog"],
  3.     ["hit","hot","lot","log","cog"]
  4.   ]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  1. class Solution {
  2.     vector<vector<string>>re;
  3.     int minlen;
  4.     void do_once(string endWord, vector<pair<vector<string>, map<char, vector<string>>> >&candi)
  5.     {
  6.         vector<pair<vector<string>, map<char, vector<string>>> >newcandi;
  7.         for (int i = 0; i < candi.size(); i++)
  8.         {
  9.             if (candi[i].first.size() + 2 <= minlen)
  10.             {
  11.                 string str = candi[i].first[candi[i].first.size()-1];
  12.                 for (map<char, vector<string>>::iterator it1 =
  13.                     candi[i].second.begin(); it1 != candi[i].second.end(); it1++)
  14.                 {
  15.                     for (int j = 0; j < it1->second.size(); j++)
  16.                     {
  17.                         if (string(it1->second[j].begin() + 1, it1->second[j].end()) == string(str.begin() + 1, str.end()))
  18.                         {
  19.                             int kk = 0;
  20.                             for (int jj = 0; jj < it1->second[j].length(); jj++)
  21.                                 if (endWord[jj] != it1->second[j][jj])
  22.                                     kk++;
  23.                             if (kk == 1)
  24.                             {
  25.                                 if (candi[i].first.size() + 2 < minlen)
  26.                                 {
  27.                                     minlen = candi[i].first.size() + 2;
  28.                                     re.clear();
  29.                                     vector<string>aa = candi[i].first;
  30.                                     aa.push_back(it1->second[j]);
  31.                                     aa.push_back(endWord);
  32.                                     re.push_back(aa);
  33.                                 }
  34.                                 else if (candi[i].first.size() + 2 == minlen)
  35.                                 {
  36.                                     vector<string>aa = candi[i].first;
  37.                                     aa.push_back(it1->second[j]);
  38.                                     aa.push_back(endWord);
  39.                                     re.push_back(aa);
  40.                                 }
  41.                             }
  42.                             else if (candi[i].first.size() + kk + 1 <= minlen)
  43.                             {
  44.                                 vector<string>aa = candi[i].first;
  45.                                 aa.push_back(it1->second[j]);
  46.                                 map<char, vector<string>>cc = candi[i].second;
  47.                                 cc[it1->first].erase(find(cc[it1->first].begin(),
  48.                                     cc[it1->first].end(), it1->second[j]));
  49.                                 newcandi.push_back(pair < vector<string>,
  50.                                     map<char, vector<string>> > (aa, cc));
  51.                             }
  52.                         }
  53.                     }
  54.                 }
  56.                 for (int j = 1; j < endWord.length(); j++)
  57.                 {
  58.                     string newstr = str;
  59.                     newstr .erase(j,1);
  60.                     for (int h =0;h< candi[i].second[newstr[0]].size();h++)
  61.                     {
  62.                         string ss = candi[i].second[newstr[0]][h];
  63.                         ss.erase(j,1);
  64.                         if (newstr == ss)
  65.                         {
  66.                             int kk = 0;
  67.                             for (int jj = 0; jj < candi[i].second[newstr[0]][h].length(); jj++)
  68.                                 if (endWord[jj] != candi[i].second[newstr[0]][h][jj])
  69.                                     kk++;
  70.                             if (kk == 1)
  71.                             {
  72.                                 if (candi[i].first.size() + 2 < minlen)
  73.                                 {
  74.                                     minlen = candi[i].first.size() + 2;
  75.                                     re.clear();
  76.                                     vector<string>aa = candi[i].first;
  77.                                     aa.push_back(candi[i].second[newstr[0]][h]);
  78.                                     aa.push_back(endWord);
  79.                                     re.push_back(aa);
  80.                                 }
  81.                                 else if (candi[i].first.size() + 2 == minlen)
  82.                                 {
  83.                                     vector<string>aa = candi[i].first;
  84.                                     aa.push_back(candi[i].second[newstr[0]][h]);
  85.                                     aa.push_back(endWord);
  86.                                     re.push_back(aa);
  87.                                 }
  88.                             }
  89.                             else if (candi[i].first.size() + kk + 1 <= minlen)
  90.                             {
  91.                                 vector<string>aa = candi[i].first;
  92.                                 aa.push_back(candi[i].second[newstr[0]][h]);
  93.                                 map<char, vector<string>>cc = candi[i].second;
  94.                                 cc[ss[0]].erase(find(cc[ss[0]].begin(),
  95.                                     cc[ss[0]].end(), candi[i].second[newstr[0]][h]));
  96.                                 newcandi.push_back(pair < vector<string>,
  97.                                     map<char, vector<string>> >(aa, cc));
  98.                             }
  99.                         }
  100.                     }
  101.                 }
  102.             }
  103.         }
  104.         candi = newcandi;
  105.     }
  106. public:
  107.     vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
  108.         minlen = wordList.size() + 2;
  109.         vector<pair<vector<string>, map<char,vector<string>>> >candi;
  110.         int kkk=0;
  111.         for (int i = 0; i < beginWord.length(); i++)
  112.             if (beginWord[i] != endWord[i])
  113.                 kkk++;
  114.         if (kkk==1)
  115.         {
  116.             vector<string>bb;
  117.             bb.push_back(beginWord);
  118.             bb.push_back(endWord);
  119.             re.push_back(bb);
  120.             return re;
  121.         }
  122.         vector<string>start;
  123.         start.push_back(beginWord);
  124.         map<char, vector<string>>bb;
  125.         for (unordered_set<string>::iterator it = wordList.begin(); it != wordList.end(); it++)
  126.             bb[(*it)[0]].push_back(*it);
  127.         candi.push_back(pair<vector<string>, map<char, vector<string>>>(start,bb));
  128.         while (!candi.empty()&&candi[0].first.size()+2<=minlen)
  129.         {
  130.             do_once(endWord, candi);
  131.         }
  132.         return re;
  133.     }
  134. };
  135. int _tmain(int argc, _TCHAR* argv[])
  136. {
  137.     string beginWord = "cet";
  138.     string    endWord = "ism";
  139.     string    words[599] = { "kid", "tag", "pup", "ail", "tun", "woo", "erg", "luz", "brr", 
  140.         "gay", "sip", "kay", "per", "val", "mes", "ohs", "now", "boa", "cet", "pal", 
  141.         "bar", "die", "war", "hay", "eco", "pub", "lob", "rue", "fry", "lit", "rex",
  142.         "jan", "cot", "bid", "ali", "pay", "col", "gum", "ger", "row", "won", "dan",
  143.         "rum", "fad", "tut", "sag", "yip", "sui", "ark", "has", "zip", "fez", "own",
  144.         "ump", "dis", "ads", "max", "jaw", "out", "btu", "ana", "gap", "cry",
  145.         "led", "abe", "box", "ore", "pig", "fie", "toy", "fat", "cal", "lie",
  146.         "noh", "sew", "ono", "tam", "flu", "mgm", "ply", "awe", "pry", "tit", 
  147.         "tie", "yet", "too", "tax", "jim", "san", "pan", "map", "ski", "ova", 
  148.         "wed", "non", "wac", "nut", "why", "bye", "lye", "oct", "old", "fin", 
  149.         "feb", "chi", "sap", "owl", "log", "tod", "dot", "bow", "fob", "for", 
  150.         "joe", "ivy", "fan", "age", "fax", "hip", "jib", "mel", "hus", "sob", 
  151.         "ifs", "tab", "ara", "dab", "jag", "jar", "arm", "lot", "tom", "sax",
  152.         "tex", "yum", "pei", "wen", "wry", "ire", "irk", "far", "mew", "wit", 
  153.         "doe", "gas", "rte", "ian", "pot", "ask", "wag", "hag", "amy", "nag", 
  154.         "ron", "soy", "gin", "don", "tug", "fay", "vic", "boo", "nam", "ave",
  155.         "buy", "sop", "but", "orb", "fen", "paw", "his", "sub", "bob", "yea", 
  156.         "oft", "inn", "rod", "yam", "pew", "web", "hod", "hun", "gyp", "wei",
  157.         "wis", "rob", "gad", "pie", "mon", "dog", "bib", "rub", "ere", "dig", 
  158.         "era", "cat", "fox", "bee", "mod", "day", "apr", "vie", "nev", "jam", 
  159.         "pam", "new", "aye", "ani", "and", "ibm", "yap", "can", "pyx", "tar", 
  160.         "kin", "fog", "hum", "pip", "cup", "dye", "lyx", "jog", "nun", "par", 
  161.         "wan", "fey", "bus", "oak", "bad", "ats", "set", "qom", "vat", "eat",
  162.         "pus", "rev", "axe", "ion", "six", "ila", "lao", "mom", "mas", "pro",
  163.         "few", "opt", "poe", "art", "ash", "oar", "cap", "lop", "may", "shy",
  164.         "rid", "bat", "sum", "rim", "fee", "bmw", "sky", "maj", "hue", "thy",
  165.         "ava", "rap", "den", "fla", "auk", "cox", "ibo", "hey", "saw", "vim", 
  166.         "sec", "ltd", "you", "its", "tat", "dew", "eva", "tog", "ram", "let",
  167.         "see", "zit", "maw", "nix", "ate", "gig", "rep", "owe", "ind", "hog",
  168.         "eve", "sam", "zoo", "any", "dow", "cod", "bed", "vet", "ham", "sis",
  169.         "hex", "via", "fir", "nod", "mao", "aug", "mum", "hoe", "bah", "hal",
  170.         "keg", "hew", "zed", "tow", "gog", "ass", "dem", "who", "bet", "gos", 
  171.         "son", "ear", "spy", "kit", "boy", "due", "sen", "oaf", "mix", "hep", 
  172.         "fur", "ada", "bin", "nil", "mia", "ewe", "hit", "fix", "sad", "rib",
  173.         "eye", "hop", "haw", "wax", "mid", "tad", "ken", "wad", "rye", "pap",
  174.         "bog", "gut", "ito", "woe", "our", "ado", "sin", "mad", "ray", "hon",
  175.         "roy", "dip", "hen", "iva", "lug", "asp", "hui", "yak", "bay", "poi",
  176.         "yep", "bun", "try", "lad", "elm", "nat", "wyo", "gym", "dug", "toe",
  177.         "dee", "wig", "sly", "rip", "geo", "cog", "pas", "zen", "odd", "nan",
  178.         "lay", "pod", "fit", "hem", "joy", "bum", "rio", "yon", "dec", "leg",
  179.         "put", "sue", "dim", "pet", "yaw", "nub", "bit", "bur", "sid", "sun",
  180.         "oil", "red", "doc", "moe", "caw", "eel", "dix", "cub", "end", "gem", 
  181.         "off", "yew", "hug", "pop", "tub", "sgt", "lid", "pun", "ton", "sol",
  182.         "din", "yup", "jab", "pea", "bug", "gag", "mil", "jig", "hub", "low", 
  183.         "did", "tin", "get", "gte", "sox", "lei", "mig", "fig", "lon", "use",
  184.         "ban", "flo", "nov", "jut", "bag", "mir", "sty", "lap", "two", "ins", 
  185.         "con", "ant", "net", "tux", "ode", "stu", "mug", "cad", "nap", "gun", 
  186.         "fop", "tot", "sow", "sal", "sic", "ted", "wot", "del", "imp", "cob", 
  187.         "way", "ann", "tan", "mci", "job", "wet", "ism", "err", "him", "all", 
  188.         "pad", "hah", "hie", "aim", "ike", "jed", "ego", "mac", "baa", "min", 
  189.         "com", "ill", "was", "cab", "ago", "ina", "big", "ilk", "gal", "tap", 
  190.         "duh", "ola", "ran", "lab", "top", "gob", "hot", "ora", "tia", "kip", 
  191.         "han", "met", "hut", "she", "sac", "fed", "goo", "tee", "ell", "not", 
  192.         "act", "gil", "rut", "ala", "ape", "rig", "cid", "god", "duo", "lin",
  193.         "aid", "gel", "awl", "lag", "elf", "liz", "ref", "aha", "fib", "oho", 
  194.         "tho", "her", "nor", "ace", "adz", "fun", "ned", "coo", "win", "tao",
  195.         "coy", "van", "man", "pit", "guy", "foe", "hid", "mai", "sup", "jay",
  196.         "hob", "mow", "jot", "are", "pol", "arc", "lax", "aft", "alb", "len",
  197.         "air", "pug", "pox", "vow", "got", "meg", "zoe", "amp", "ale", "bud", 
  198.         "gee", "pin", "dun", "pat", "ten", "mob" };
  199.     unordered_set<string> wordList;
  200.     for (int i = 0; i < 599; i++)
  201.         wordList.insert(words[i]);
  202.     Solution sl;
  203.     vector<vector<string>>re=sl.findLadders(beginWord, endWord, wordList);
  204.     system("pause");
  205.     return 0;
  206. }

问题一 内存消耗太大

问题二 太慢

思路，换用双向广度优先搜索，从beginword和endword同时开始搜索，在找到第一个答案的那一层找到所有答案后即可返回。

  1. class Solution {
  2. public:
  3.     vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
  4.         vector<vector<string>>re;
  5.         if (beginWord == endWord || beginWord.length() == 1)
  6.         {
  7.             vector<string>rr;
  8.             rr.push_back(beginWord);
  9.             rr.push_back(endWord);
  10.             re.push_back(rr);
  11.             return re;
  12.         }
  13.         int wl = beginWord.length();
  14.         for (int i = 0; i < wl; i++)
  15.         {
  16.             string s1(beginWord), s2(endWord);
  17.             s1.erase(i, 1); s2.erase(i, 1);
  18.             if (s1 == s2)
  19.             {
  20.                 vector<string>rr;
  21.                 rr.push_back(beginWord);
  22.                 rr.push_back(endWord);
  23.                 re.push_back(rr);
  24.                 return re;
  25.             }
  26.         }
  28.         vector<string>words(wordList.begin(), wordList.end());
  29.         map<pair<string,int>, vector<int>>changelist;
  30.         for (int i = 0; i < words.size(); i++)
  31.         {
  32.             for (int j = 0; j < words[0].length(); j++)
  33.             {
  34.                 string s = words[i];
  35.                 s.erase(j, 1);
  36.                 changelist[pair<string, int>(s,j)].push_back(i);
  37.             }
  38.         }
  39.         vector<int>a, b;
  40.         for (int i = 0; i < words.size(); i++)
  41.             a.push_back(i);
  42.         map<string, vector<vector<int>>>head, tail;
  43.         head[beginWord].push_back(b);
  44.         tail[endWord].push_back(b);
  45.         bool flag = true;
  46.         int k = 0;
  47.         while (k < words.size() && flag)
  48.         {
  49.             k++;
  50.             if (tail.size()>head.size())
  51.             {
  52.                 map<string, vector<vector<int>>>newhead;
  53.                 for (map<string, vector<vector<int>>>::iterator ii = head.begin(); ii != head.end(); ii++)
  54.                 {
  55.                     for (int j = 0; j < ii->second.size(); j++)
  56.                     {
  57.                         for (int h = 0; h < wl; h++)
  58.                         {
  59.                             string s = ii->first;
  60.                             s.erase(h, 1);
  61.                             for (int f = 0; f < changelist[pair<string, int>(s,h)].size(); f++)
  62.                             {
  63.                                 if (words[changelist[pair<string, int>(s,h)][f]] != ii->first)
  64.                                 {
  65.                                     vector<int>::iterator ite = find(ii->second[j].begin(),
  66.                                         ii->second[j].end(), changelist[pair<string, int>(s,h)][f]);
  67.                                     if (ite == ii->second[j].end())
  68.                                     {
  69.                                         map<string, vector<vector<int>>>::iterator nn =
  70.                                             tail.find(words[changelist[pair<string, int>(s,h)][f]]);
  71.                                         if (nn != tail.end())
  72.                                         {
  73.                                             for (int g = 0; g < nn->second.size(); g++)
  74.                                             {
  75.                                                 set<int>aa;
  76.                                                 set<int>a1(ii->second[j].begin(), ii->second[j].end());
  77.                                                 set<int>a2(nn->second[g].begin(), nn->second[g].end());
  78.                                                 set_intersection(a1.begin(), a1.end(),
  79.                                                     a2.begin(), a2.end(), inserter(aa, aa.begin()));
  80.                                                 if (aa.empty() && (a1.size()>0 || a2.size()>0))
  81.                                                 {
  82.                                                     flag = false;
  83.                                                     vector<string>sl;
  84.                                                     sl.push_back(beginWord);
  85.                                                     for (int d = 0; d < ii->second[j].size(); d++)
  86.                                                         sl.push_back(words[ii->second[j][d]]);
  87.                                                     //sl.push_back(words[changelist[s][f]]);
  88.                                                     for (int d = nn->second[g].size() - 1; d >= 0; d--)
  89.                                                         sl.push_back(words[nn->second[g][d]]);
  90.                                                     sl.push_back(endWord);
  91.                                                     if (find(re.begin(), re.end(), sl) == re.end())
  92.                                                         re.push_back(sl);
  93.                                                 }
  94.                                             }
  95.                                         }
  96.                                         if (flag)
  97.                                         {
  98.                                             vector<int>xx = ii->second[j];
  99.                                             xx.push_back(changelist[pair<string, int>(s,h)][f]);
  100.                                             newhead[words[changelist[pair<string, int>(s,h)][f]]].push_back(xx);
  101.                                         }
  102.                                     }
  103.                                 }
  104.                             }
  105.                         }
  106.                     }
  107.                 }
  108.                 //f = !f;
  109.                 head = newhead;
  110.             }
  111.             else
  112.             {
  113.                 map<string, vector<vector<int>>>newtail;
  114.                 for (map<string, vector<vector<int>>>::iterator ii = tail.begin(); ii != tail.end(); ii++)
  115.                 {
  116.                     for (int j = 0; j < ii->second.size(); j++)
  117.                     {
  118.                         for (int h = 0; h < wl; h++)
  119.                         {
  120.                             string s = ii->first;
  121.                             s.erase(h, 1);
  122.                             for (int f = 0; f < changelist[pair<string, int>(s,h)].size(); f++)
  123.                             {
  124.                                 if (words[changelist[pair<string, int>(s,h)][f]] != ii->first)
  125.                                 {
  126.                                     vector<int>::iterator ite = find(ii->second[j].begin(), ii->second[j].end(), 
  127.                                         changelist[pair<string, int>(s,h)][f]);
  128.                                     if (ite == ii->second[j].end())
  129.                                     {
  130.                                         map<string, vector<vector<int>>>::iterator nn = head.find(words[changelist[pair<string, int>(s, h)][f]]);
  131.                                         if (nn != head.end())
  132.                                         {
  133.                                             for (int g = 0; g < nn->second.size(); g++)
  134.                                             {
  135.                                                 set<int>aa;
  136.                                                 set<int>a1(ii->second[j].begin(), ii->second[j].end());
  137.                                                 set<int>a2(nn->second[g].begin(), nn->second[g].end());
  138.                                                 set_intersection(a1.begin(), a1.end(),
  139.                                                     a2.begin(), a2.end(), inserter(aa, aa.begin()));
  140.                                                 if (aa.empty() && (a1.size()>0 || a2.size()>0))
  141.                                                 {
  142.                                                     flag = false;
  143.                                                     vector<string>sl;
  144.                                                     sl.push_back(beginWord);
  145.                                                     for (int d = 0; d< nn->second[g].size(); d++)
  146.                                                         sl.push_back(words[nn->second[g][d]]);
  147.                                                     //sl.push_back(words[changelist[s][f]]);
  148.                                                     for (int d = ii->second[j].size() - 1; d >= 0; d--)
  149.                                                         sl.push_back(words[ii->second[j][d]]);
  150.                                                     sl.push_back(endWord);
  151.                                                     if (find(re.begin(), re.end(), sl) == re.end())
  152.                                                         re.push_back(sl);
  153.                                                 }
  154.                                             }
  155.                                         }
  156.                                         if (flag)
  157.                                         {
  158.                                             vector<int>xx = ii->second[j];
  159.                                             xx.push_back(changelist[pair<string, int>(s, h)][f]);
  160.                                             newtail[words[changelist[pair<string, int>(s, h)][f]]].push_back(xx);
  161.                                         }
  162.                                     }
  163.                                 }
  164.                             }
  165.                         }
  166.                     }
  167.                 }
  168.                 //f = !f;
  169.                 tail = newtail;
  170.             }
  171.         }
  172.         return re;
  173.     }
  174. };

accepted

发表评论

表情：
评论列表 （有 0 条评论，233人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Word Ladder--LeetCode

    这道题看似一个关于字符串操作的题目，其实要解决这个问题得用图的方法。我们先给题目进行图的映射，顶点则是每个字符串，然后两个字符串如果相差一个字符则我们进行连边。接下来看看这个方

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 249 阅读