[关闭]
@HaomingJiang 2018-07-22T05:39:48.000000Z 字数 2152 阅读 784
  1. class Solution {
  2. public:
  3. vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
  4. vector<string> word_path;
  5. vector<vector<int>> path_prev;
  6. vector<int> path_prev_0;
  7. vector<int> level;
  8. int flag = 0;
  9. word_path.push_back(beginWord);
  10. path_prev_0.push_back(-1);
  11. path_prev.push_back(path_prev_0);
  12. level.push_back(0);
  13. list<string> new_wordlist;
  14. for(int i = 0;i<wordList.size();i++)
  15. new_wordlist.push_back(wordList[i]);
  16. auto wordlist_iter = new_wordlist.begin();
  17. while(wordlist_iter!= new_wordlist.end())
  18. {
  19. if(*wordlist_iter == beginWord)
  20. {
  21. new_wordlist.erase(wordlist_iter);
  22. break;
  23. }
  24. wordlist_iter++;
  25. }
  26. bool success = false;
  27. flag = 0;
  28. for(int clevel = 0;;clevel++)
  29. {
  30. int level_begin_flag = flag;
  31. while(true)
  32. {
  33. if(flag>=word_path.size()) break;
  34. if(level[flag] > clevel) break;
  35. string ori_word = word_path[flag];
  36. flag++;
  37. if(success) continue;
  38. wordlist_iter = new_wordlist.begin();
  39. while(wordlist_iter!= new_wordlist.end())
  40. {
  41. int diff = sim(*wordlist_iter, ori_word);
  42. if(diff==1){
  43. vector<int> path_prev_0;
  44. word_path.push_back(*wordlist_iter);
  45. path_prev.push_back(path_prev_0);
  46. level.push_back(clevel+1);
  47. if(*wordlist_iter == endWord)
  48. {
  49. success = true;
  50. break;
  51. }
  52. wordlist_iter = new_wordlist.erase(wordlist_iter);
  53. }
  54. else{
  55. wordlist_iter++;
  56. }
  57. }
  58. }
  59. // no new node found
  60. if(flag>=word_path.size()) break;
  61. //update path_prev
  62. for(int i = flag;i<word_path.size();i++)
  63. {
  64. for(int j = level_begin_flag;j<flag;j++){
  65. //cout << word_path[i] << " vs " <<word_path[j] << " "<<sim(word_path[i], word_path[j])<< endl;
  66. if(sim(word_path[i], word_path[j])==1)
  67. path_prev[i].push_back(j);
  68. }
  69. }
  70. //for(int i = 0;i<word_path.size();i++)
  71. // cout << word_path[i] << "["<< level[i]<< "] ";
  72. //cout<<endl;
  73. //cout<<"---------\n";
  74. if(success) break;
  75. }
  76. vector<vector<string>> sol;
  77. if(!success) return sol;
  78. vector<string> c_sol;
  79. dfs(sol,word_path,path_prev,c_sol, word_path.size()-1);
  80. return sol;
  81. }
  82. void dfs(vector<vector<string>> &sol, vector<string> &word_path, vector<vector<int>> &path_prev, vector<string> c_sol, int id){
  83. //cout<<id<<" :";
  84. //for(auto i : path_prev[id])
  85. // cout<<i<<' ';
  86. //cout<<endl;
  87. c_sol.insert(c_sol.begin(),word_path[id]);
  88. if(id==0){
  89. sol.push_back(c_sol);
  90. return;
  91. }
  92. for(auto i : path_prev[id]){
  93. dfs(sol,word_path,path_prev,c_sol,i);
  94. }
  95. }
  96. int sim(string a, string b){
  97. int diff = 0;
  98. for(int i=0;i<a.size();i++){
  99. if(a[i] != b[i])
  100. diff++;
  101. if(diff==2)
  102. break;
  103. }
  104. return diff;
  105. }
  106. };
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注