title
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:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
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.
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
solution
有待优化，速度太慢了
class Solution {
public:
bool isconnect(string a, string b) {
int diff = 0;
for (int i = 0; i < a.length(); i++) {
if (a[i] != b[i]) {
diff++;
}
}
return diff == 1;
}
void build(vector<vector<int>> &v, vector<string>& worldList) {
for (int i = 0; i < worldList.size(); i++) {
for (int j = 0; j < worldList.size(); j++) {
if (isconnect(worldList[i], worldList[j])) {
v[i].push_back(j);
}
}
}
}
int getShortestPath(int start,int end,vector<vector<int>> &v,int n) {
int len = 1;
bool *visit = new bool[n + 1];
fill(visit, visit + n + 1, false);
visit[start] = true;
queue<int> q;
q.push(start);
while (!q.empty()) {
len++;
int size = q.size();
while (size--) {
int p = q.front();
q.pop();
for (auto next : v[p]) {
if (next == end) {
return len;
}
if (!visit[next]) {
q.push(next);
visit[next] = true;
}
}
}
}
return 0;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
wordList.push_back(beginWord);
vector<vector<int>> v(wordList.size());
int start = wordList.size()-1, end = -1, n = wordList.size();
for (int i = 0; i < n; i++) {
if (wordList[i] == endWord) {
end = i;
}
}
if (end == -1) {
return 0;
}
cout << start << " " << end << endl;
build(v, wordList);
return getShortestPath(start, end, v, n);
}
};
java
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
wordList.add(beginWord);
int N = wordList.size();
int start = N - 1;
int end = 0;
while (end < N && !wordList.get(end).equals(endWord)) {
end++;
}
if (end == N) {
return 0;
}
List<Integer>[] graphic = buildGraphic(wordList);
return getShortestPath(graphic, start, end);
}
private List<Integer>[] buildGraphic(List<String> wordList) {
int N = wordList.size();
List<Integer>[] graphic = new List[N];
for (int i = 0; i < N; i++) {
graphic[i] = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (isConnect(wordList.get(i), wordList.get(j))) {
graphic[i].add(j);
}
}
}
return graphic;
}
private boolean isConnect(String s1, String s2) {
int diffCnt = 0;
for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diffCnt++;
}
}
return diffCnt == 1;
}
private int getShortestPath(List<Integer>[] graphic, int start, int end) {
Queue<Integer> queue = new LinkedList<>();
boolean[] marked = new boolean[graphic.length];
queue.add(start);
marked[start] = true;
int path = 1;
while (!queue.isEmpty()) {
int size = queue.size();
path++;
while (size-- > 0) {
int cur = queue.poll();
for (int next : graphic[cur]) {
if (next == end) {
return path;
}
if (marked[next]) {
continue;
}
marked[next] = true;
queue.add(next);
}
}
}
return 0;
}