Solution { public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { wordList.remove(endWord); if (isOneLetterDiff(beginWord, endWord)) { return singletonList(Arrays.asList(beginWord, endWord)); } else { Node<String> root = new Node<>(endWord, null); List<Node<String>> leaves = singletonList(root); while (!isFound) { leaves = goOneLevelDeeperForEach(leaves, beginWord, wordList); if (leaves.size() == 0) { break; } } return leaves.stream() .map(Solution::allWords) .collect(Collectors.toList()); } }  List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList); static boolean isOneLetterDiff(String a, String b);  }
@Test public void shouldHandleNoAnswerInput() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("hot", "dog", new HashSet<>(Arrays.asList("hot", "dog"))); assertThat(ladders.size(), is(0)); }
@Test public void exampleInput() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("hit", "cog", new HashSet<>(Arrays.asList("hot", "cog", "dot", "dog", "hit", "lot", "log"))); assertThat(ladders.get(0), hasItems("hit", "hot", "dot", "dog", "cog")); assertThat(ladders.get(1), hasItems("hit", "hot", "lot", "log", "cog")); }
@Test public void anotherInput() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("git", "php", new HashSet<>(Arrays.asList("gip", "pip", "pit"))); assertThat(ladders.get(0), hasItems("git", "gip", "pip", "php")); assertThat(ladders.get(1), hasItems("git", "pit", "pip", "php")); }
@Test public void shouldAvoidBackLooping() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("leet", "code", new HashSet<>(Arrays.asList("lest", "leet", "lose", "code", "lode", "robe", "lost"))); assertThat(ladders.get(0), hasItems("leet", "lest", "lost", "lose", "lode", "code")); }
@Test public void oneLetterWords() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("a", "c", new HashSet<>(Arrays.asList("a", "b", "c"))); assertThat(ladders.get(0), hasItems("a", "c")); }
@Test public void onlyReturnShortest() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("kiss", "tusk", new HashSet<>(Arrays.asList("kiss", "diss", "disk", "dusk", "tusk", "miss", "muss", "musk"))); assertThat(ladders.get(0), hasItems("kiss", "diss", "disk", "dusk", "tusk")); assertThat(ladders.get(1), hasItems("kiss", "miss", "muss", "musk", "tusk")); }
@Test public void onlyReturnShortest2() throws Exception { Solution solution = new Solution(); List<List<String>> ladders = solution.findLadders("cat", "fin", new HashSet<>(Arrays.asList("cat", "fat", "fit", "fin", "fan", "can", "mat", "mit"))); assertThat(ladders.get(0), hasItems("cat", "can", "fan", "fin")); assertThat(ladders.get(1), hasItems("cat", "fat", "fan", "fin")); assertThat(ladders.get(2), hasItems("cat", "fat", "fit", "fin")); }