Leetcode Word Ladder - c++编程基础

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time

Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.

All words contain only lowercase alphabetic characters.

没见过这样的题目的话，也很难搞懂他的要求的，所以要问问题：

1 中间的选单词，是否可以乱序？ -- 可以的，可以随便在字典里面抽那个单词都可以。

2 是否需要计算所抽单词的中间距离？不需要

好难的一道题目，虽然思想就是层序遍历树的思想，但是细节太多，很容易导致出错，而且有人使用同样的思想做的却会超时。

原因有几个：

1 细节需要优化好 - 我增加层间标志的做法就超时了

但是使用两个队列的做法不超时，好奇怪的题目。

2 对于原字典dict可以作破坏性操作-就是可以delete其中的元素

这样操作，速度提高了好几百ms，也就是这几百ms导致是否超时。

光debug，都花费我一两个小时，看到是曾相似的题目，居然也这么难，差那么一点点啊！

下面是我参考Leetcode论坛写的代码，认为已经优化的程序了，用时600ms左右。

class Solution {
public:
	int ladderLength(string start, string end, unordered_set
      
        &dict) 
	{
		if (start == end) return 1;
		int n = start.size();
		if (n<1 || n != end.size()) return 0;

		queue
       
         qs; qs.push(start); dict.erase(start); int minLen = 2; int lv1 = 1; int lv2 = 0; while (!qs.empty()) { string s = qs.front(); qs.pop(); lv1--; for (int i = 0; i < n; i++) { //注意：要很小心，位置不能错了，每一次t都需要重置回s char oriChar = s[i]; for (char a = 'a'; a <= 'z'; a++) { if (a == oriChar) continue; s[i] = a; if (s == end) return minLen; if (dict.find(s)!=dict.end()) { qs.push(s); dict.erase(s); lv2++; } } s[i] = oriChar; } if (lv1 == 0) { lv1 = lv2; lv2 = 0; ++minLen; } } return 0; } };

变形要求题目：如果需要找的路径必须是中间的某个字字符串，可以不相邻，但是不能乱序，那么就用得着下面的程序了。

1 使用动态规划法简历路径表

2 根据路径表查找结果，保留最小路径

这样的要求应该比原题还要困难。

class Solution {
public:
	int ladderLength(string start, string end, unordered_set
      
        &dict) 
	{
		if (isLadder(start, end)) return 2;
		int n = dict.size();
		vector
       
         >ta; generatePath(ta, dict, start, end); int minLen = INT_MAX; for (int i = 0; i < n; i++) { if (ta[n][i]) { if (ta[i][n]) return 3; else { for (int j = i+1; j < n; j++) { if (ta[j][n] && findPath(ta, i, j)) { minLen = min(minLen, j-i+2); } } } } } return minLen==INT_MAX  0:minLen; } bool findPath(vector
        
          > &ta, int left, int right) { for (int i = left; i <= right; i++) { if (ta[left][i] && ta[i][right]) return true; } return false; } void generatePath(vector
         
           > &ta, unordered_set
          
            &dict, string &s, string &e) { int n = dict.size(); ta.resize(n+1, vector
           
            (n+1)); auto it = dict.end(); for (int i = n-1; i >= 0; i--) { it--; //一定要放在这里，不能放在for的末尾，因为it==dict.begin()的时候是不可减的，会出现iterator not decrementable的错误 //如果使用it = dict.end(),会出错：iterator not dereferencable if (isLadder(s, *it)) ta[n][i] = true; if (isLadder(*it, e)) ta[i][n] = true; auto it2 = dict.end(); for (int j = n-1; j >= i; j--) { it2--; if (isLadder(*it, *it2)) ta[i][j] = true; } } } bool isLadder(string a, string b) { int c = 0; for (int i = 0; i < a.size(); i++) { if (a[i] != b[i]) c++; if (c>=2) return false; } return true; } void generatePath2(vector
            
              > &ta, unordered_set
             
               &dict, string &s, string &e) { int n = dict.size(); ta.resize(n+1, vector
              
               (n+1)); auto it = dict.rbegin(); for (int i = n-1; i >= 0; i--, it++) { if (isLadder(s, *it)) ta[n][i] = true; if (isLadder(*it, e)) ta[i][n] = true; auto it2 = dict.rbegin(); for (int j = n-1; j >= i; j--, it2++) { if (isLadder(*it, *it2)) ta[i][j] = true; } } } }; int main() { string a = "jife"; string b = "jifekfl"; Solution solu; unordered_set
               
                 us; us.insert(a); a = "jeei"; us.insert(a); a = "jeir"; us.insert(a); a = "jefr"; us.insert(a); a = "reii"; us.insert(a); a = "rhob"; us.insert(a); a = "rhab"; us.insert(a); for (auto x:us) { cout<
                
                  >vb; string s1 = "jeih"; string s2 = "hefr"; solu.generatePath2(vb, us, s1, s2); for (auto x:vb) { for (auto y:x) cout<