# LeetCode Kill Process

LeetCode Kill Process
Given n processes, each process has a unique PID (process id) and its PPID (parent process id).
Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.
We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.
Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.
Example 1:

```Input:
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
3
/   \
1     5
/
10
Kill 5 will also kill 10.
```

Note:

1. The given kill id is guaranteed to be one of the given PIDs.
2. n >= 1.

```class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_multimap<int, int> umm;
for (int i = 0; i < pid.size(); ++i) {
umm.insert(pair<int, int>(ppid[i], pid[i]));
}
vector<int> ans;
queue<int> q;
q.push(kill);
while (!q.empty()) {
int id = q.front();
q.pop();
ans.push_back(id);
auto r = umm.equal_range(id);
for (auto i = r.first; i != r.second; ++i)q.push(i->second);
}
return ans;
}
};
```

# LeetCode Friend Circles

LeetCode Friend Circles
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:

```Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
```

Example 2:

```Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
```

Note:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

```class Solution {
private:
int n;
vector<int> parent;
void init() {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find_set(int x) {
if (parent[x] != x)
parent[x] = find_set(parent[x]);
return parent[x];
}
void union_set(int u, int v) {
parent[find_set(u)] = find_set(v);
}
public:
int findCircleNum(vector<vector<int>>& M) {
n = M.size();
init();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (M[i][j] == 1) {
union_set(i, j);
}
}
}
set<int> circles;
for (int i = 0; i < n; ++i)circles.insert(find_set(i)); // 注意最后还要find一下找到代表
return circles.size();
}
};
```

# hihoCoder 1519-逃离迷宫II

hihoCoder 1519-逃离迷宫II

### 输出

```5 5
S.#.T
.....
.....
.....
.....```

`2`

```#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
int ans = INT_MAX;
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<char>> visited(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ {-1,0},{1,0},{0,-1},{0,1} }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
bool ok(int x, int y) {
if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
return false;
}
void dfs(int sx,int sy, int step) {
for (int i = 0; i < 4; ++i) {
int newx = sx + dirs[i][0], newy = sy + dirs[i][1];
if (ok(newx, newy) && visited[newx][newy] == '0') {
visited[newx][newy] = '1';
bool done = false;
while (ok(newx, newy)) {
visited[newx][newy] = '1';
if (newx == endx&&newy == endy) {
done = true;
break;
}
newx = newx + dirs[i][0], newy = newy + dirs[i][1];
}
if (done) {
ans = min(ans, step);
}
else {
dfs(newx + opdirs[i][0], newy + opdirs[i][1], step + 1);  // 往回走一步再递归
}
while (!(newx == sx&&newy == sy)) {
if (ok(newx, newy))visited[newx][newy] = '0'; // 复位
newx = newx + opdirs[i][0], newy = newy + opdirs[i][1];
}
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
char c;
for (int i = 0; i < n; ++i) {
scanf("%c", &c);
for (int j = 0; j < m; ++j) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
else if (maze[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
visited[startx][starty] = '1';
dfs(startx, starty, 0);
if (ans == INT_MAX)printf("-1\n");
else printf("%d\n", ans);
return 0;
}
```

```#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 505;
int n, m;
int startx, starty, endx, endy;
typedef struct P {
int x, y, step;
P(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};
vector<vector<char>> maze(MAXN, vector<char>(MAXN, '0'));
vector<vector<int>> dirs{ { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } }; //up,down,left,right
vector<vector<int>> opdirs{ { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }; // 反方向
set<int> points;
bool ok(int x, int y) {
if (x >= 0 && x < n&&y >= 0 && y < m&&maze[x][y] != '#')return true;
return false;
}
int id(int x, int y) {
return x*n + y;
}
int bfs() {
queue<P> q;
P p(startx, starty, 0);
q.push(p);
while (!q.empty()) {
p = q.front();
q.pop();
points.insert(id(p.x, p.y));
for (int i = 0; i < dirs.size(); ++i) {
int newx = p.x + dirs[i][0], newy = p.y + dirs[i][1];
while (ok(newx, newy)) {
if (newx == endx&&newy == endy) {
return p.step;
}
newx = newx + dirs[i][0], newy = newy + dirs[i][1];
}
int cornorx = newx + opdirs[i][0], cornory = newy + opdirs[i][1]; // 往回走一步
if (points.find(id(cornorx, cornory)) == points.end()) {
P tmp(cornorx, cornory, p.step + 1);
q.push(tmp);
}
}
}
return -1;
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
char c;
for (int i = 0; i < n; ++i) {
scanf("%c", &c);
for (int j = 0; j < m; ++j) {
scanf("%c", &maze[i][j]);
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
else if (maze[i][j] == 'T') {
endx = i;
endy = j;
}
}
}
printf("%d\n", bfs());
return 0;
}
```

# LeetCode Minimum Height Trees

LeetCode Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains `n` nodes which are labeled from `0` to `n - 1`. You will be given the number `n` and a list of undirected `edges` (each edge is a pair of labels).
You can assume that no duplicate edges will appear in `edges`. Since all edges are undirected, `[0, 1]` is the same as `[1, 0]` and thus will not appear together in `edges`.
Example 1:
Given `n = 4`, `edges = [[1, 0], [1, 2], [1, 3]]`

```        0
|
1
/ \
2   3
```

return `[1]`
Example 2:
Given `n = 6`, `edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]`

```     0  1  2
\ | /
3
|
4
|
5
```

return `[3, 4]`

Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

给定一个无向无环图，问以哪个顶点为根形成的有根树的树高是最小的，如果有多个这样的最小高度的有根树，则输出所有这样的根节点。
很有意思的一题，需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个，我想了想，应该最多只有两个吧。可以用反证法，假设有3个，则这3个根肯定会形成环，具体原因大家可以在纸上画个图举个例子就知道了。
然后我由题目的样例想到的是，把图转换为有根的最小高度的树，根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数，然后选两个度数最高的节点，对这两个点DFS求以他们为根时的树高，如果树高相同，说明这两个点都是答案，否则取树高更高的节点作为根节点。
但是很可惜，代码提交之后WA，错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。

```8     3
\    \
2----0----5----6----7----9
/    /
4    1```

在上图中，度数最多的前两个点是0和2，但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。
参考网上的题解，好巧妙呀。这种解法类似于剥洋葱，一层一层把叶子节点剥离掉，最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的，没剥掉一层，相当于树高减一，一直减，到最后还剩下的节点肯定就是根节点了。比如上图中，第一层剥掉8,3,9,4,1，变成下图

`2----0----5----6----8`

第二层剥掉之后变成下图

`0----5----6`

第三层剥掉之后就只剩下5号节点了，所以以5号节点为根，树的高度最低，只有3，而我的解法算出来的根节点0的树高是4，不是最小的。

`5`

剥洋葱的解法用BFS来实现就非常方便了，BFS天然就是一层循环就是剥掉一层。
代码中，初始时，我们把图转换为类似邻接表的结果，但是每个vector里存的是unordered_set，而不是list，因为剥洋葱的时候，比如第一层时剥掉8号节点时，我们同时需要把2号节点的邻接表中的8号节点删掉，所以用unordered_set.erase就非常方便。后面循环时，没剥一层，我们就检查一下，把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时，剩余的节点就是有根树的根节点。如果剩余两个节点，说明这两个节点的高度是一样的，都是正确答案。
代码如下：

```class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1)return{ 0 };
int m = edges.size();
vector<unordered_set<int>> graph(n, unordered_set<int>());
for (int i = 0; i < m; ++i) {
graph[edges[i].first].insert(edges[i].second);
graph[edges[i].second].insert(edges[i].first);
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (graph[i].size() == 1) q.push(i);
}
while (n > 2) {
int t = q.size();
n -= t;
while (t--) {
int leaf = q.front();
q.pop();
for (auto par : graph[leaf]) { // only one par
graph[par].erase(leaf);
if (graph[par].size() == 1)q.push(par);
}
}
}
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.front());
q.pop();
}
return ans;
}
};
```

本代码提交AC，用时79MS。

# LeetCode Evaluate Division

LeetCode Evaluate Division
Equations are given in the format `A / B = k`, where `A` and `B` are variables represented as strings, and `k` is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return `-1.0`.
Example:
Given `a / b = 2.0, b / c = 3.0.`
queries are: `a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .`
return `[6.0, 0.5, -1.0, 1.0, -1.0 ].`
The input is: `vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries `, where `equations.size() == values.size()`, and the values are positive. This represents the equations. Return `vector<double>`.
According to the example above:

```equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].```

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

给定一系列的除法表达式，要计算另一些除法表达式的结果。比如知道a/b=2.0,b/c=3.0，问a/c=?。
本题的解法是把一系列表达式转换为图，比如a/b=2.0转换为a指向b的边，边的值为2.0，同时b指向a的边的值为1/2.0。如果要求a/c，则在图中找一条a到c的边，并且把走过的边的值乘起来。
构建图的过程先把表达式中的string编码成int，然后把已知的直连边加入到图中。对于要查询的边start/target，首先判断一下两个端点是否在图中，如果至少有一个端点不在图中，则无法求值，返回-1。否则，在图中DFS或BFS找到target，走过的路径乘积就是结果。
题目说明所有values都是正数，所以不存在除0问题。
DFS代码如下：

```class Solution {
private:
bool dfs(vector<vector<double>>& graph, int start, int x, int y, int target) {
graph[start][y] = graph[start][x] * graph[x][y];
graph[y][start] = 1.0 / graph[start][y];
if(y == target)return true;
int n = graph.size();
for(int i = 0; i < n; ++i){
if(graph[start][i] == 0 && graph[y][i] != 0){
if(dfs(graph, start, y, i, target))return true;
}
}
return false;
}
double helper(vector<vector<double>>& graph, int start, int target) {
if (start == target)return 1.0;
else if (graph[start][target] != 0.0)return graph[start][target];
int n = graph.size();
for (int y = 0; y < n; ++y) {
if (y == start)continue;
if (graph[start][y] != 0.0) {
if (dfs(graph, start, start, y, target))return graph[start][target];
}
}
return -1.0;
}
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
int cnt = 0, n = equations.size();
unordered_map<string, int> hash;
for (int i = 0; i < n; ++i) {
if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
}
vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
for (int i = 0; i < n; ++i) {
int x = hash[equations[i].first], y = hash[equations[i].second];
graph[x][x] = 1;
graph[y][y] = 1;
graph[x][y] = values[i];
graph[y][x] = 1.0 / values[i];
}
vector<double> ans;
for (int i = 0; i < queries.size(); ++i) {
if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
else {
int x = hash[queries[i].first], y = hash[queries[i].second];
ans.push_back(helper(graph, x, y));
}
}
return ans;
}
};
```

本代码提交AC，用时3MS。
BFS代码如下：

```class Solution {
private:
double bfs(vector<vector<double>>& graph, int start, int target) {
if (start == target)return 1.0;
else if (graph[start][target] != 0.0)return graph[start][target];
int n = graph.size();
queue<int> q;
for(int x = 0; x < n; ++x){
if(x != start && graph[start][x] != 0)q.push(x);
}
while(!q.empty()){
int x = q.front();
if(x == target) return graph[start][target];
q.pop();
for(int y = 0; y < n; ++y){
if(graph[start][y] == 0 && graph[x][y] != 0){
graph[start][y] = graph[start][x] * graph[x][y];
graph[y][start] = 1.0 / graph[start][y];
q.push(y);
}
}
}
return -1.0;
}
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
int cnt = 0, n = equations.size();
unordered_map<string, int> hash;
for (int i = 0; i < n; ++i) {
if (hash.find(equations[i].first) == hash.end())hash[equations[i].first] = cnt++;
if (hash.find(equations[i].second) == hash.end())hash[equations[i].second] = cnt++;
}
vector<vector<double>> graph(cnt, vector<double>(cnt, 0));
for (int i = 0; i < n; ++i) {
int x = hash[equations[i].first], y = hash[equations[i].second];
graph[x][x] = 1;
graph[y][y] = 1;
graph[x][y] = values[i];
graph[y][x] = 1.0 / values[i];
}
vector<double> ans;
for (int i = 0; i < queries.size(); ++i) {
if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end())ans.push_back(-1.0);
else {
int x = hash[queries[i].first], y = hash[queries[i].second];
ans.push_back(bfs(graph, x, y));
}
}
return ans;
}
};
```

本代码提交AC，用时0MS，类似的题BFS显然要比DFS快，而且这题用BFS思路更清晰。

# LeetCode 01 Matrix

LeetCode 01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:

```0 0 0
0 1 0
0 0 0
```

Output:

```0 0 0
0 1 0
0 0 0
```

Example 2:
Input:

```0 0 0
0 1 0
1 1 1
```

Output:

```0 0 0
0 1 0
1 2 1
```

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

给定一个0/1矩阵，要求每个点到其最近的0的距离。显然，如果自身是0的话，到最近的0的距离就是0，所以这里只需要求当cell不为0时，它到最近的0的距离。
显然是个BFS的题，从点(i,j)往外广度搜索，第一个遇到0时，走过的步数就是和0的最短距离；没遇到0时，不断的把点加入到队列中。
自定义一个MyPoint结构体，保存点的坐标，以及从出发点到该点的步数。注意本题不需要visited数组，visited数组的目的是保证在BFS时不走之前走过的点，但是BFS走过的路径肯定有那种没走之前走过的点的路径，这样的路径到达0的距离肯定会比走重复点的路径到达0的距离要短。所以不用visited也能找到最短距离。
代码如下：

```typedef struct MyPoint {
int x, y;
int step;
MyPoint(int x_, int y_, int step_) :x(x_), y(y_), step(step_) {};
};
class Solution {
private:
int bfs(int i, int j, vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
MyPoint p(i, j, 0);
queue<MyPoint> qp;
qp.push(p);
while (!qp.empty()) {
p = qp.front();
if (matrix[p.x][p.y] == 0)return p.step;
qp.pop();
if (p.x - 1 >= 0) {
MyPoint tmp(p.x - 1, p.y, p.step + 1);
qp.push(tmp);
}
if (p.x + 1 < m) {
MyPoint tmp(p.x + 1, p.y, p.step + 1);
qp.push(tmp);
}
if (p.y - 1 >= 0) {
MyPoint tmp(p.x, p.y - 1, p.step + 1);
qp.push(tmp);
}
if (p.y + 1 < n) {
MyPoint tmp(p.x, p.y + 1, p.step + 1);
qp.push(tmp);
}
}
}
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = 0;
if (m > 0)n = matrix[0].size();
if (m == 0 || n == 0)return vector<vector<int>>();
vector<vector<int>> ans(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] != 0) {
ans[i][j] = bfs(i, j, matrix);
}
}
}
return ans;
}
};
```

本代码提交AC，用时276MS。

# LeetCode Find Largest Value in Each Tree Row

LeetCode Find Largest Value in Each Tree Row
You need to find the largest value in each row of a binary tree.
Example:

```Input:
1
/ \
3   2
/ \   \
5   3   9
Output: [1, 3, 9]```

给定一棵二叉树，找出每层的最大值。
简单题，直接BFS，在每一层找最大值。代码如下：

```class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
if (!root)return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int largest = INT_MIN, n = q.size();
while (n--) {
TreeNode* front = q.front();
q.pop();
largest = max(largest, front->val);
if (front->left)q.push(front->left);
if (front->right)q.push(front->right);
}
ans.push_back(largest);
}
return ans;
}
};
```

本代码提交AC，用时13MS。

# LeetCode Find Bottom Left Tree Value

LeetCode Find Bottom Left Tree Value
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:

```Input:
2
/ \
1   3
Output:
1
```

Example 2:

```Input:
1
/ \
2   3
/   / \
4   5   6
/
7
Output:
7
```

Note: You may assume the tree (i.e., the given root node) is not NULL.

找出一棵二叉树最后一行的最左边元素。
简单题，直接BFS，每层保存队列第一个元素，BFS结束之后，就能得到最后一行的第一个元素。
代码如下：

```class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int ans = 0;
while (!q.empty()) {
int n = q.size();
ans = q.front()->val;
while (n--) {
TreeNode* front = q.front();
q.pop();
if (front->left)q.push(front->left);
if (front->right)q.push(front->right);
}
}
return ans;
}
};
```

本代码提交AC，用时12MS。

# LeetCode Binary Tree Zigzag Level Order Traversal

LeetCode Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

```[
[3],
[20,9],
[15,7]
]```

本题还是树的层次遍历，但是稍微有点不一样，要求奇数层从左往右输出，偶数层从右往左输出。常规的层次遍历使用BFS实现，即队列，这里要求颠倒顺序，马上想到用堆栈。
维护一个left2right布尔变量，当tru时，把孩子从左往右压栈，这样下一层的输出顺序就是从右往左了；当为false时相反。这里我们还需要用到两个堆栈，分别保存当前层和下一层的结果。
talk is cheap, show you the code!

```class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root)return ans;
bool left2right = true;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()) {
stack<TreeNode*> stk2;
vector<int> cand;
size_t n = stk.size();
for (size_t i = 0; i < n; ++i) {
TreeNode* top = stk.top();
stk.pop();
if (!top)continue;
cand.push_back(top->val);
if (left2right) {
stk2.push(top->left);
stk2.push(top->right);
}
else {
stk2.push(top->right);
stk2.push(top->left);
}
}
left2right = !left2right;
if (!cand.empty()) ans.push_back(cand);
stk = stk2;
}
return ans;
}
};
```

本代码提交AC，用时6MS。

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,
Given:
beginWord = `"hit"`
endWord = `"cog"`
wordList = `["hot","dot","dog","lot","log","cog"]`
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.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

很有意思的一个题。给定两个单词beginWord和endWord，以及一个字典数组，问从beginWord到endWord，最少需要多少次变换，每次只能变换一个字母，而且变换的单词都必须存在于字典数组中。
很明显是一个BFS题，从beginWord开始广搜，直到第一次搜到endWord时停止，此时走过的变换数就是最小变换数。因为广搜会搜索所有的空间，那么第一次到达endWord也就是最早到达的。
当然BFS的题也都能用DFS来做，但是DFS显然会慢，想想便知，DFS必须搜索完一条完整的路径才能知道结果，才能进入下一条路径开始搜索；而BFS是每条路径同步进行，只要有一条路径到达，就结束搜索。
常规的BFS代码如下：

```typedef struct Item {
string cur;
string used;
int step;
Item(string c, string u, int s) :cur(c), used(u), step(s) {};
};
class Solution {
public:
bool differOne(const string &s1, const string &s2) {
int cnt = 0;
for (size_t i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) {
++cnt;
if (cnt > 1)return false;
}
}
return cnt == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
size_t n = wordList.size();
queue<Item> q;
Item it(beginWord, string(n, '0'), 1);
q.push(it);
while (!q.empty()) {
Item t = q.front();
q.pop();
if (t.cur == endWord)return t.step;
for (size_t i = 0; i < n; ++i) {
if (t.used[i] == '0'&&differOne(t.cur, wordList[i])) {
string newUsed = t.used;
newUsed[i] = '1';
Item tmp(wordList[i], newUsed, t.step + 1);
q.push(tmp);
}
}
}
return 0;
}
};
```

本代码很好理解，定义一个结构体Item，cur为当前到达的单词，用一个和wordList大小相同的字符串used表示走到cur时走过的单词，step表示当前走过的步数。很可惜，这个版本的代码提交MLE，超空间了。肯定是因为Item这个结构体太大了，两个string，一个int。
后来想到一个优化的方法，当某条路径path1走到单词cur时，其他路径就没必要再经过cur了，因为一旦经过cur，必定后续步骤和path1后续要走的路径就相同了，造成了重复搜索。所以我们走过每个单词时，可以直接将该单词置空，这样后续就不会再走该路了，同时这样也不需要Item结构体了。新版代码如下：

```class Solution {
public:
bool differOne(const string &s1, const string &s2) {
int cnt = 0;
for (size_t i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) {
++cnt;
if (cnt > 1)return false;
}
}
return cnt == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
size_t n = wordList.size();
queue<string> q;
q.push(beginWord);
int step = 1;
while (!q.empty()) {
size_t len = q.size();
for (size_t i = 0; i < len; ++i) {
string t = q.front();
q.pop();
if (t == endWord)return step;
for (size_t j = 0; j < wordList.size(); ++j) {
if (wordList[j] != ""&&differOne(t, wordList[j])) {
q.push(wordList[j]);
wordList[j] = "";
}
}
}
++step;
}
return 0;
}
};
```

本代码提交AC，用时632MS。