4
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! Asking for code to be written is off-topic, so I have removed part of your question. \$\endgroup\$ – 200_success Apr 29 '15 at 12:41
4
\$\begingroup\$

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;
    }
}

There's a few improvements here.

First,

if (diffLetters == 1) {
    return true;
} else {
    return false;
}

"If condition is true, return true, else if condition is not true AKA false, return false." Such statements can be replaced with "return condition".

return diffLetters == 1;

Second,

    char[] baseChars = baseWord.toCharArray();
    char[] checkChars = checkWord.toCharArray();
    int diffLetters = 0;

    if (baseChars.length != checkChars.length) {
        return false;
    }

This guard clause can be done sooner. There's no need to convert to char array before checking the length.

if(baseWord.length != checkWord.length){
    return false;
}

Third,

    for (int i = 0; i < baseChars.length; i++) {
        if (baseChars[i] != checkChars[i]) {
            diffLetters++;
        }
    }

you can exit early once you know more than 1 letter differs.

    for (int i = 0; i < baseChars.length; i++) {
        if (baseChars[i] != checkChars[i]) {
            diffLetters++;
            if(diffLetters > 1){
                return false;
            }
        }
    }
\$\endgroup\$
1
\$\begingroup\$

You could build (undirected and unweighted) graph, in which nodes correspond to words in dictionary, and there is (once again, undirected) edges between nodes whose words differ only by one character. Once you have the graph, finding the shortest chain is equivalent to finding a shortest undirected path in that graph.

\$\endgroup\$
  • 2
    \$\begingroup\$ Without any comments on why this approach would be better than the approach used by the OP, this is not a valid answer, as it's not a code review. \$\endgroup\$ – Pimgd Apr 29 '15 at 12:46
  • \$\begingroup\$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. \$\endgroup\$ – tim Apr 29 '15 at 14:13
  • \$\begingroup\$ I think this is a good approach. The answer could be significantly improved, by for example adding reasoning about time complexities, but I think it is a completely valid answer. \$\endgroup\$ – Simon Forsberg Apr 29 '15 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.