LevDistance

Main.java

import java.io.*;
import java.sql.SQLOutput;
import java.util.*;

public class Main {

	private static Set<String> words;
	private static Map<String, Set<String>> neighbors;

	private static final char[] ALPHABET = "qwertyuiopasdfghjklzxcvbnm".toCharArray();

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new FileReader(new File("dictionary.txt")));

		words = new HashSet<>();

		neighbors = new HashMap<>();

		long startTime = System.currentTimeMillis();

		String line;
		while ((line = reader.readLine()) != null) {
			words.add(line.trim().toLowerCase());
		}

		System.out.println("Done adding " + words.size() + " words to the set in " +
				(System.currentTimeMillis() - startTime) + " ms.");

		createNeighborsMap();

		System.out.println("Done creating " + neighbors.size() + " neighbors map in " +
				(System.currentTimeMillis() - startTime) + " ms.");

//		testNeighbors();
		askLevDistance();
	}

	private static void createNeighborsMap() {
		for (String word : words) {
			Set<String> neighboringWords = new HashSet<>();

			for (int i = 0; i < word.length(); i++) {
				String prefix = word.substring(0, i);
				for (int j = 0; j < ALPHABET.length; j++) {
					String newWord = prefix + ALPHABET[j] + word.substring(i);
					if (words.contains(newWord)) {
						neighboringWords.add(newWord);
					}
				}
				for (int j = 0; j < ALPHABET.length; j++) {
					String newWord = prefix + word.substring(i + 1);
					if (words.contains(newWord)) {
						neighboringWords.add(newWord);
					}
				}
			}
			if (neighboringWords.size() > 0) {
				neighbors.put(word, neighboringWords);
			}
		}
	}

	private static void testNeighbors() {
		Scanner input = new Scanner(System.in);

		while (true) {
			System.out.print("Word: ");
			String word = input.nextLine();
			System.out.println(neighbors.get(word));
		}
	}

	private static void askLevDistance() {
		Scanner input = new Scanner(System.in);

		while (true) {
			System.out.print("Word 1: ");
			String word1 = input.nextLine().toLowerCase();
			System.out.print("Word 2: ");
			String word2 = input.nextLine().toLowerCase();

			if (word1.equals(word2)) {
				System.out.println("FOUND with distance = 0");
			} else if (!neighbors.containsKey(word1)) {
				System.out.println("Word '" + word1 + "' is not in the dictionary.");
			} else if (!neighbors.containsKey(word2)) {
				System.out.println("Word '" + word2 + "' is not in the dictionary.");
			}

			findLevDistance(word1, word2);
		}
	}

	private static void findLevDistance(String start, String end) {
		Queue<Word> wordsToVisit = new LinkedList<>();
		Set<String> searched = new HashSet<>();

		wordsToVisit.add(new Word(start, 0));
		searched.add(start);

		LinkedList<Set<String>> layers = new LinkedList<>();

		Set<String> firstLayer = new HashSet<>();
		firstLayer.add(start);
		layers.add(firstLayer);

		Set<String> bottomLayer = firstLayer;

		int distance = 1;

		while (!bottomLayer.isEmpty()) {
			// for every word, add its neighbors to the next layer
			Set<String> nextLayer = new HashSet<>();

			for (String word : bottomLayer) {
				if (neighbors.containsKey(word)) {
					for (String neighbor : neighbors.get(word)) {
						if (neighbor.equals(end)) {
							System.out.println("FOUND with distance = " + distance);
							return;
						} else if (!searched.contains(neighbor)) {
							nextLayer.add(neighbor);
							searched.add(neighbor);
						}
					}
				}
			}

			layers.addLast(nextLayer);
			bottomLayer = nextLayer;
			distance++;
		}

		/*


		while (!wordsToVisit.isEmpty()) {
			// remove front word of the list
			Word front = wordsToVisit.remove();
			int distance = front.distance;

			if (neighbors.containsKey(front.word)) {
				for (String neighbor : neighbors.get(front.word)) {
					if (!searched.contains(neighbor)) {
						if (neighbor.equals(end)) {
							System.out.println("FOUND with distance = " + distance + 1);
							return;
						} else {
							wordsToVisit.add(new Word(neighbor, distance + 1));
							searched.add(neighbor);
						}
					}
				}
			}

		}*/

		System.out.println("No possible path, searched until distance = " + distance);
	}

	private static class Word {
		public String word;
		public int distance;

		public Word(String word, int distance) {
			this.word = word;
			this.distance = distance;
		}
	}
}