Created
May 15, 2015 09:34
-
-
Save yusufaytas/e538590491ab7250d0e9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.yusufaytas.test.intercom; | |
import java.util.ArrayList; | |
import java.util.HashMap; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Set; | |
public class PathsBetweenWords { | |
public List<List<String>> getPaths(String beginWord, String endWord, Set<String> words) { | |
List<List<String>> allPaths = new ArrayList<List<String>>(); | |
Map<String, Set<String>> wordMap = createWordMap(words); | |
getPaths(allPaths, new ArrayList<String>(), beginWord, endWord, wordMap); | |
return allPaths; | |
} | |
private void getPaths(List<List<String>> allPaths, List<String> path, String beginWord, String endWord, | |
Map<String, Set<String>> wordMap) { | |
List<String> currentPath = new ArrayList<String>(path); | |
currentPath.add(beginWord); | |
if(beginWord.equals(endWord)){ | |
allPaths.add(currentPath); | |
} | |
else{ | |
Set<String> nextWords = wordMap.get(beginWord); | |
for (String nextWord : nextWords) { | |
if(!currentPath.contains(nextWord)){ | |
//avoid the loops. | |
getPaths(allPaths, currentPath, nextWord, endWord, wordMap); | |
} | |
} | |
} | |
} | |
private Map<String, Set<String>> createWordMap(Set<String> words){ | |
Map<String, Set<String>> wordMap = new HashMap<String, Set<String>>(words.size()); | |
for (String word : words) { | |
Set<String> nextWords = new HashSet<String>(); | |
for (String nextWord : words) { | |
if(isItNextWord(word, nextWord)){ | |
nextWords.add(nextWord); | |
} | |
} | |
wordMap.put(word, nextWords); | |
} | |
return wordMap; | |
} | |
private boolean isItNextWord(String word, String nextWord){ | |
boolean firstChange = false; | |
for (int i = 0; i < word.length(); i++) { | |
if(word.charAt(i) != nextWord.charAt(i)){ | |
if(firstChange){ | |
return false; | |
} | |
firstChange = true; | |
} | |
} | |
return firstChange; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment