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.
EXAMPLE
Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

Thoughts:
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.

Codes:

	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>();
		Q.add(src);
		visited.add(src);
		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)) {
					visited.add(o);
					Q.add(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))
					results.add(newStr);
			}
		}
		return results;
	}
About these ads

One Comment (+add yours?)

  1. Trackback: transform one word into another – Breadth-First-Search | 456 vcd studio 2013 Renee

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 59 other followers

%d bloggers like this: