How to Solve Word Chains Problem

Problem description:

A word chain consists of a set of words ordered so that each word differs by only one letter from the words directly before and after it. The one letter difference can be either an insertion, a deletion, or a substitution. Here is an example word chain:

Write a function which takes a set of words, and returns true if they can be arranged into one continuous word chain, and false if they cannot.

Sample Input:

{"hat", "coat", "dog", "cat", "oat", "cot", "hot", "hog"}
{"cot", "hot", "bat", "fat"}
{"to", "top", "stop", "tops", "toss"}
{"spout", "do", "pot", "pout", "spot", "dot"}

Sample Output:

true
false
false
true

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 WordChains {
    private static int editDistance(String str1, String str2) {
        int lenStr1 = str1.length();
        int lenStr2 = str2.length();
        if (lenStr1 == 0) {
            return lenStr2;
        }
        if (lenStr2 == 0) {
            return lenStr1;
        }
        int cost = 0;
        if (!str1.substring(lenStr1 - 1).equals(str2.substring(lenStr2 - 1))) {
            cost = 1;
        }
        return minimum(editDistance(str1.substring(0, lenStr1 - 1), str2) + 1,
            editDistance(str1, str2.substring(0, lenStr2 - 1)) + 1,
            editDistance(str1.substring(0, lenStr1 - 1), str2.substring(0, lenStr2 - 1)) + cost);

    }

    private static int minimum(int i1, int i2, int i3) {
        return Math.min(Math.min(i1, i2), i3);
    }
    
    private static Map<Integer, Set<Integer>> buildMap(String[] words) {
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < words.length; i++) {
            map.put(i, new HashSet<Integer>());
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (words[i].equals(words[j])) {
                    continue;
                }
                if (editDistance(words[i], words[j]) == 1) {
                    map.get(i).add(j);
                }
            }
        }
        return map;
    }
    
    public static boolean wordChains(String[] words) {
        Map<Integer, Set<Integer>> map = buildMap(words);
        Set<List<Integer>> result = new HashSet<List<Integer>>();
        for (Map.Entry<Integer, Set<Integer>> e : map.entrySet()) {
            List<Integer> processed = new ArrayList<>();
            processed.add(e.getKey());
            recurseWordChains(map, e.getValue(), processed, result);
        }
        
        if (result.size() == 0) {
            return false;
        }
        
        for (List<Integer> list : result) {
            for (int i : list) {
                System.out.print(words[i] + " ");
            }
            System.out.println();
        }
        return true;
    }

    private static void recurseWordChains(Map<Integer, Set<Integer>> map,
        Set<Integer> set, List<Integer> processed, Set<List<Integer>> result) {
        if (processed.size() == map.size()) {
            result.add(processed);
        }
        
        for (int i : set) {
            if (processed.contains(i)) {
                continue;
            }
            List<Integer> newList = new ArrayList<>(processed);
            newList.add(i);
            recurseWordChains(map, map.get(i), newList, result);
        }
    }
    
    private static void printSeperator() {
        for (int i = 0; i < 72; i++) {
            System.out.print("-");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        System.out.println(wordChains(new String[]{"cat", "cot", "coat", "oat", "hat", "hot", "hog", "dog"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"cot", "hot", "bat", "fat"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"to", "top", "stop", "tops", "toss"}));
        printSeperator();
        System.out.println(wordChains(new String[]{"spout", "do", "pot", "pout", "spot", "dot"}));
        printSeperator();
    }
}

Output:

oat hat cat coat cot hot hog dog 
hat oat cat coat cot hot hog dog 
dog hog hot hat cat oat coat cot 
hat oat coat cat cot hot hog dog 
dog hog hot cot coat oat hat cat 
dog hog hot hat oat cat cot coat 
dog hog hot cot coat cat hat oat 
dog hog hot cot coat cat oat hat 
coat cot cat oat hat hot hog dog 
dog hog hot cot cat coat oat hat 
cat cot coat oat hat hot hog dog 
dog hog hot cot coat oat cat hat 
dog hog hot hat oat cat coat cot 
dog hog hot hat oat coat cot cat 
dog hog hot hat oat coat cat cot 
cot coat cat oat hat hot hog dog 
cot cat coat oat hat hot hog dog 
cot coat oat cat hat hot hog dog 
dog hog hot cot cat hat oat coat 
dog hog hot hat cat cot coat oat 
oat coat cot cat hat hot hog dog 
coat oat hat cat cot hot hog dog 
cat hat oat coat cot hot hog dog 
hat cat oat coat cot hot hog dog 
true
--------------------------------
false
--------------------------------
false
--------------------------------
do dot pot pout spout spot 
do dot pot spot spout pout 
spot spout pout pot dot do 
pout spout spot pot dot do 
true
--------------------------------