脸书店面

发面经 攒人品

只问了一道题，word l

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

了一道题，是不是就没戏了。。。

我以前面过也是一道题，不会的，听上去你写的不错，应该没问题，可能他觉得已经够了把，希望一切顺利！

是所有可能路径, 那就用DFS最方便了.  要是输出所有最短路径还挺麻烦的..

1. public class WordLadderIII {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         WordLadderIII w = new WordLadderIII();
   
5.         Set<String> dict = new HashSet<>();
   
6.         dict.add("hot");
   
7.         dict.add("dot");
   
8.         dict.add("dog");
   
9.         dict.add("lot");
   
10.         dict.add("log");
    
11.         dict.add("cog");
    
12.         List<List<String>> res = w.getAllLadders("hit", "cog", dict);
    
13.         for (List<String> list : res) {
    
14.             for (String s : list) {
    
15.                 System.out.print(s + "->");
    
16.             }
    
17.             System.out.println();
    
18.         }
    
19.     }
    
20. 
    
21.     public List<List<String>> getAllLadders(String start, String end, Set<String> dict) {
    
22.         List<List<String>> res = new ArrayList<>();
    
23.         if (dict == null || dict.size() == 0) {
    
24.             return res;
    
25.         }
    
26.         dict.remove(start);
    
27.         List<String> list = new ArrayList<>();
    
28.         list.add(start);
    
29.         helper(res, start, end, dict, list);
    
30.         return res;
    
31.     }
    
32. 
    
33.     public void helper(List<List<String>>  res, String start, String end, Set<String> set, List<String> list) {
    
34.         if (start.equals(end)) {
    
35.             res.add(new ArrayList<>(list));
    
36.             return;
    
37.         }
    
38. 
    
39.         for (int i = 0; i < start.length(); i++) {
    
40.             StringBuilder sb = new StringBuilder(start);
    
41.             for (char c = 'a'; c <= 'z'; c++) {
    
42.                 sb.setCharAt(i, c);
    
43.                 String newStr = sb.toString();
    
44.                 if (set.contains(newStr)) {
    
45.                     set.remove(newStr);
    
46.                     list.add(newStr);
    
47.                     helper(res, newStr, end, set, list);
    
48.                     list.remove(list.size() - 1);
    
49.                     set.add(newStr);
    
50.                 }
    
51.             }
    
52.         }
    
53.     }
    
54. }
    

复制代码