There is a file with two words with the same length. Call them first and last.
Also there is a file - dictionary with a lot of different words.
public class Main {
// args[0] - is path to file with first and last words
// args[1] - is path to file with dictionary
public static void main(String[] args) {
try {
List<String> firstLastWords = FileParser.getWords(args[0]);
// System.out.println(firstLastWords);
int sizeOfWords = firstLastWords.get(1).length();
List<String> dictionary = WordHandler.getSameLengthWords(
FileParser.getWords(args[1]), sizeOfWords);
// System.out.println(dictionary);
Tree tree = new Tree(dictionary, firstLastWords);
tree.print();
tree.findShortestSuitableChain();
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
/////////////////
public class FileParser {
public FileParser() {
}
final static Charset ENCODING = StandardCharsets.UTF_8;
public static List<String> getWords(String filePath) throws IOException {
List<String> list = new ArrayList<String>();
Path path = Paths.get(filePath);
try (BufferedReader reader = Files.newBufferedReader(path, ENCODING)) {
String line = null;
while ((line = reader.readLine()) != null) {
String line1 = line.trim().replaceAll("\uFEFF", "");
list.add(line1);
}
reader.close();
for (int i = 0; i < list.size(); i++) {
if (list.get(i).length() <= 1) {
list.remove(i);
}
}
}
return list;
}
}
//////////////
public class WordHandler {
public WordHandler() {
}
public static boolean isOneLetterDifference(String baseWord,String checkWord) {
char[] baseChars = baseWord.toCharArray();
char[] checkChars = checkWord.toCharArray();
int diffLetters = 0;
if (baseChars.length != checkChars.length) {
return false;
}
for (int i = 0; i < baseChars.length; i++) {
if (baseChars[i] != checkChars[i]) {
diffLetters++;
}
}
if (diffLetters == 1) {
return true;
} else {
return false;
}
}
public static List<String> getSameLengthWords(List<String> list, int length) {
List<String> list1 = new ArrayList<String>();
for (String st : list) {
if (st.length() == length) {
list1.add(st);
}
}
return list1;
}
} }
}
////////////////
public class Tree {
public Tree() {
}
public Tree(List<String> dictionary, List<String> firstLastWords) {
this.dictionary = dictionary;
this.firstLastWords = firstLastWords;
this.rootNode = new Node(firstLastWords.get(0), null);
this.lastWord = firstLastWords.get(1);
this.buildBranch(rootNode);
}
private List<String> dictionary;
private List<String> firstLastWords;
private Node rootNode;
private String lastWord;
public List<String> getDictionary() {
return dictionary;
}
public void setDictionary(List<String> dictionary) {
this.dictionary = dictionary;
}
public List<String> getFirstLastWords() {
return firstLastWords;
}
public void setFirstLastWords(List<String> firstLastWords) {
this.firstLastWords = firstLastWords;
}
public Node getRootNode() {
return rootNode;
}
public void setRootNode(Node rootNode) {
this.rootNode = rootNode;
}
// sets suitable children of node
private void writeChildrens(Node node) {
List<String> currentDictionary = new ArrayList<String>(dictionary);
// currentDictionary - is dictionary for this current Node
// currentDictionary = dictionary - (this node data + all data of parent
// nodes)
currentDictionary.removeAll(node.returnParentData());
List<Node> children = new ArrayList<Node>();
String data = node.getData();
for (String st : currentDictionary) {
if (WordHandler.isOneLetterDifference(data, st)) {
children.add(new Node(st, node));
}
}
node.setChildren(children);
}
// build whole tree branch by branch
private void buildBranch(Node node) {
writeChildrens(node);
List<Node> children = node.getChildren();
if (children.size() > 0) {
for (Node child : children) {
buildBranch(child);
}
}
}
// find all chains of tree, which last node's data = lastWord
private void findSuitableChains(Node node, Map<Integer, List<String>> map) {
List<Node> children = node.getChildren();
if (children.size() > 0) {
for (Node child : children) {
if (child.getData().equals(lastWord)) {
int i = map.size();
map.put(i, child.returnParentData());
} else {
findSuitableChains(child, map);
}
}
}
}
// prints whole tree from rootNode
public void print() {
rootNode.print();
}
// from all suitable chains finds shortest and prints it
public void findShortestSuitableChain() {
Map<Integer, List<String>> map = new LinkedHashMap<Integer, List<String>>();
findSuitableChains(rootNode, map);
// find index of shortest chain
int shortChainIndex = 0;
int dictionarySize = dictionary.size();
for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
if (entry.getValue().size() < dictionarySize) {
dictionarySize = entry.getValue().size();
shortChainIndex = entry.getKey();
}
}
Collections.reverse(map.get(shortChainIndex));
List<String> list = new ArrayList<String>(map.get(shortChainIndex));
for (String s : list) {
System.out.println(s);
}
}
}
///////////
public class Node {
public Node(String data) {
this.data = data;
}
public Node(String data, Node parent) {
this.data = data;
this.parent = parent;
}
public Node(String data, Node parent, List<Node> children) {
this.data = data;
this.parent = parent;
this.children = children;
}
private String data;
private Node parent;
private List<Node> children;
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public List<Node> getChildren() {
return children;
}
public void setChildren(List<Node> children) {
this.children = children;
}
// returns list of strings containing data of node and all parents of node
// this method is used when we find dictionary of current node
// (we have to delete words that have been already used upwards in the branch)
public List<String> returnParentData() {
Node node = this;
List<String> list = new ArrayList<String>();
while (node.getParent() != null) {
list.add(node.getData());
node = node.getParent();
if (node.getParent() == null) {
list.add(node.getData());
}
}
return list;
}
// prints tree from this node
public void print() {
print("", true);
}
private void print(String prefix, boolean isTail) {
System.out.println(prefix + (isTail ? "└── " : "├── ") + data);
for (int i = 0; i < children.size() - 1; i++) {
children.get(i).print(prefix + (isTail ? " " : "│ "), false);
}
if (children.size() > 0) {
children.get(children.size() - 1).print(
prefix + (isTail ? " " : "│ "), true);
}
}
}
///////////
Test with words in example give next:
///////////
|-topTest with words in example give next:
|-top
├── pop
│ └── pot
│ └── dot
└── ton
├── son
└── son
top
ton
son
