1 public class Solution {
 2     List<List<String>> finalList = new ArrayList<>();
 3 
 4     public static void main(String[] args) {
 5         Solution s = new Solution();
 6         System.out.println(s.getPath("face", "book"));
 7     }
 8 
 9     public List<List<String>> getPath(String s, String e) {
10         List<String> list = new ArrayList<String>();
11         helper(s, e, list, new HashSet<String>());
12         return finalList;
13     }
14 
15     public void helper(String s, String e, List<String> list, Set<String> set) {
16         if (set.contains(s) || (list.size() != 0 && list.get(list.size() - 1).equals(e))) return;
17         list.add(s);
18         set.add(s);
19 
20         if (s.equals(e)) {
21             finalList.add(new ArrayList<String>(list));
22         }
23 
24         List<String> dicts = getWords(s);
25         for (String str : dicts) {
26             helper(str, e, list, set);
27         }
28 
29         list.remove(s);
30         set.remove(s);
31     }
32 
33     public List<String> getWords(String str) {
34         List<String> list1 = new ArrayList<String>();
35 
36         if (str.equals("face")) {
37             list1.add("foce");
38             list1.add("fack");
39         } else if (str.equals("foce")) {
40             list1.add("face");
41             list1.add("fook");
42         } else if (str.equals("fack")) {
43             list1.add("fook");
44             list1.add("faok");
45         } else if (str.equals("fook")) {
46             list1.add("fack");
47             list1.add("book");
48         } else if (str.equals("faok")) {
49             list1.add("foce");
50             list1.add("book");
51         }
52         return list1;
53     }
54 }