Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.16 KB | None | 0 0
  1. public int ladderLength(String start, String end, HashSet<String> dict) {
  2. if(start==null || end==null || start.length()==0 || end.length()==0 || start.length()!=end.length())
  3. return 0;
  4. LinkedList<String> queue = new LinkedList<String>();
  5. HashSet<String> visited = new HashSet<String>();
  6. int level= 1;
  7. int lastNum = 1;
  8. int curNum = 0;
  9. queue.offer(start);
  10. visited.add(start);
  11. while(!queue.isEmpty())
  12. {
  13. String cur = queue.poll();
  14. lastNum--;
  15. for(int i=0;i<cur.length();i++)
  16. {
  17. char[] charCur = cur.toCharArray();
  18. for(char c='a';c<='z';c++)
  19. {
  20. charCur[i] = c;
  21. String temp = new String(charCur);
  22. if(temp.equals(end))
  23. return level+1;
  24. if(dict.contains(temp) && !visited.contains(temp))
  25. {
  26. curNum++;
  27. queue.offer(temp);
  28. visited.add(temp);
  29. }
  30. }
  31. }
  32. if(lastNum==0)
  33. {
  34. lastNum = curNum;
  35. curNum = 0;
  36. level++;
  37. }
  38. }
  39. return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement