Transform one word into another by changing only one letter at a time

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

This is essentially a modified version of Breadth-First-Search. For each word, its braches are those words that can be tranformed from it by changing only one letter. We need to keep track of a route-map so that when we hit the destination, we can backtrack to retrieve the route we have been.


	public static List<String> transform(String src, String des,
			Set<String> dictionary) {
		Queue<String> Q = new LinkedList<String>();
		Set<String> visited = new HashSet<String>();
		Map<String, String> routes = new HashMap<String, String>();
		while (!Q.isEmpty()) {
			String t = Q.poll();
			if (t.equals(des)) {
				LinkedList<String> list = new LinkedList<String>();
				while (t != null) {
					list.add(0, t);
					t = routes.get(t);
				return list;
			for (String o : getAllTransformations(t, dictionary)) {
				if (!visited.contains(o)) {
					routes.put(o, t);
		return null;

	private static List<String> getAllTransformations(String src,
			Set<String> dictionary) {
		List<String> results = new LinkedList<String>();
		for (int i = 0; i < src.length(); ++i) {
			for (char c = 'A'; c <= 'Z'; ++c) {
				String newStr = src.substring(0, i) + c + src.substring(i + 1);
				if (!src.equals(newStr) && dictionary.contains(newStr))
		return results;

2 Comments (+add yours?)

  1. Trackback: transform one word into another – Breadth-First-Search | 456 vcd studio 2013 Renee
  2. Kevin
    Apr 20, 2014 @ 20:26:01

    Did you just copy paste code from Gayle Laakmann Book, without quoting any reference!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: