public class Solution {
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null || end == null || dict == null
|| start.length() != end.length()) {
return 0;
}
if (oneDiff(start, end)) {
return 2;
}
return helper(start, end, dict, 2);
}
public boolean oneDiff(String left, String right) {
int sameNumber = 0;
if (left == null || right == null) {
return false;
}
if (left.length() != right.length()) {
return false;
}
for (int i = 0; i < left.length(); i++) {
if (left.charAt(i) == right.charAt(i)) {
sameNumber++;
}
}
if (sameNumber == left.length() - 1) {
return true;
}
return false;
}
public int helper(String start, String end, Set<String> dict, int level) {
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
HashMap<String,Integer> route = new HashMap<String,Integer>();
route.put(start,0);
while (!queue.isEmpty()) {
int qSize = queue.size();
for (int i = 0; i < qSize; i++) {
String cur = queue.poll();
for (int j = 0; j < cur.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) {
if (cur.charAt(j) == c) {
continue;
}
StringBuffer sb = new StringBuffer(cur);
sb.setCharAt(j, c);
String nowStr = sb.toString();
if (nowStr.equals(end)) {
return level++;
}
if (dict.contains(nowStr)
&& !route.containsKey(nowStr)) {
queue.offer(nowStr);
route.put(nowStr,0);
}
}
}
}
level++;
}
return 0;
}
}
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null || end == null || dict == null
|| start.length() != end.length()) {
return 0;
}
if (oneDiff(start, end)) { return 2;
}
return helper(start, end, dict, 2); } public boolean oneDiff(String left, String right) {
int sameNumber = 0;
if (left == null || right == null) {
return false;
}
if (left.length() != right.length()) {
return false;
}
for (int i = 0; i < left.length(); i++) {
if (left.charAt(i) == right.charAt(i)) {
sameNumber++;
}
}
if (sameNumber == left.length() - 1) {
return true;
}
return false;
} public int helper(String start, String end, Set<String> dict, int level) {
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
HashMap<String,Integer> route = new HashMap<String,Integer>();
route.put(start,0);
while (!queue.isEmpty()) {
int qSize = queue.size();
for (int i = 0; i < qSize; i++) {
String cur = queue.poll();
for (int j = 0; j < cur.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) {
if (cur.charAt(j) == c) {
continue;
}
StringBuffer sb = new StringBuffer(cur);
sb.setCharAt(j, c);
String nowStr = sb.toString(); if (nowStr.equals(end)) {
return level++;
}
if (dict.contains(nowStr)
&& !route.containsKey(nowStr)) {
queue.offer(nowStr);
route.put(nowStr,0); }
}
} }
level++;
}
return 0;
}
}
之后发现这个太丑了，用了算法导论上的方法，找一个东西来记录层数：
public class Solution {
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null || end == null || dict == null
|| start.length() != end.length()) {
return 0;
}
return helper(start, end, dict, 1);
}
public int helper(String start, String end, Set<String> dict, int level) {
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
HashMap<String, Integer> route = new HashMap<String, Integer>();
route.put(start, 1);
while (!queue.isEmpty()) {
String cur = queue.poll();
int curLevel = route.get(cur);
for (int j = 0; j < cur.length(); j++) {
for (char c = 'a'; c <= 'z'; c++) {
if (cur.charAt(j) == c) {
continue;
}
StringBuffer sb = new StringBuffer(cur);
sb.setCharAt(j, c);
String nowStr = sb.toString();
if (nowStr.equals(end)) {
return ++curLevel;
}
if (dict.contains(nowStr) && !route.containsKey(nowStr)) {
queue.offer(nowStr);
route.put(nowStr, curLevel + 1);
}
}
}
}
return 0;
}
}