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.
The task is to find shortest chain of words from dictionary from first word to last so that two neighboring words different just one character. All words of chain must be the same length.
For example:
Input:
// first and last words
top
son
// dictionary
top
son
pop
pot
dot
ton
son
soft
task
Output:
top
ton
son
My program works, but I am not sure that it is good code. So I ask you to view my code.
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:
|-top
├── pop
│ └── pot
│ └── dot
└── ton
├── son
└── son
top
ton
son
