2014
11-19

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

1. Only one letter can be changed at a time
2. 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.

//LeetCode, Word Ladder
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
int ladderLength(const string& start, const string &end,
const unordered_set<string> &dict) {
queue<string> current, next;    // 当前层，下一层
unordered_set<string> visited;  // 判重

int level = 0;  // 层次
bool found = false;

auto state_is_target = [&](const string &s) {return s == end;};
auto state_extend = [&](const string &s) {
vector<string> result;

for (size_t i = 0; i < s.size(); ++i) {
string new_word(s);
for (char c = 'a'; c <= 'z'; c++) {
if (c == new_word[i]) continue;

swap(c, new_word[i]);

if (dict.count(new_word) > 0 &&
!visited.count(new_word)) {
result.push_back(new_word);
visited.insert(new_word);
}
swap(c, new_word[i]); // 恢复该单词
}
}

return result;
};

current.push(start);
while (!current.empty() && !found) {
++level;
while (!current.empty() && !found) {
const string str = current.front();
current.pop();

const auto& new_states = state_extend(str);
for (const auto& state : new_states) {
next.push(state);
if (state_is_target(state)) {
found = true; //找到了
break;
}
}
}
swap(next, current);
}
if (found) return level + 1;
else return 0;
}
};


Java代码:

public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
if (dict.size() == 0)
return 0;
String tag = new String();
int len = 1;
while(queue.size() > 1){
String top = queue.pop();
if(top == tag){
len++;
continue;
}
if(top.equals(end)){
return len;
}
for(int i=0; i<top.length(); i++){
char[] currCharArr = top.toCharArray();
for(char c='a'; c<='z'; c++){
currCharArr[i] = c;
String newWord = new String(currCharArr);
if(dict.contains(newWord)){
dict.remove(newWord);//删除掉遍历过的单词
}
}
}
}
return 0;
}
} 

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

4. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;