CareerCup

The approach is to build a graph with vertices as words. An edge exists between two vertices if the two words differ by only one character. Once the graph is constructed, you need to a BFS to obtain the path/count the number of nodes between two words.

To construct the graph, we pass the dictionary as a Set<String>

public Map<String, List<String>> constructGraph(Set<String> set) {

	Map<String, List<String>> map = new HashMap<String, List<String>>();
	for (String str : set) {
		for (String match : set) {
			if (oneCharDiff(str, match)) {
				List<String> list = map.get(str);
				if (list == null) {
					list = new LinkedList<String>();
					map.put(str, list);
				}
				list.add(match);
			}
		}
	}
	return map;
}

In the above code, the function oneCharDiff returns true if there is exactly one character difference between two words.

The following code navigates to the path using the above function,

public static void path(String input, String output, Set<String> set) {

	Map<String, List<String>> map = constructGraph(set);
	Map<String, String> path = new HashMap<String, String>();
	Queue<Word> queue = new LinkedList<>();
	String parent = null;
	queue.add(new Word(input, parent));
	while (!queue.isEmpty()) {
		Word word = queue.remove();
		input = word.original;
		parent = word.parent;
		if (!path.containsKey(input)) {
			path.put(input, parent);
			if (input.equals(output)) {
				System.out.println(output);
				while (parent != null) {
					System.out.println(parent);
					parent = path.get(parent);
				}
				return;
			}
			List<String> list = map.get(input);
			if (list != null) {
				for (String child : list)
					queue.add(new Word(child, input));
			}
		}
	}
	System.out.println("No such path found");
}

Word is a simple class with 2 members - String original and String parent. This is used to print the order of the path followed.

Time complexity : O(n^2) when constructing the graph. Any suggestions to improve the solution are welcome. There is another way to handle this problem using the backtracking method but i'm sure the complexity would be exponential in that case.

The answer is the number of letters in start word which are different from the letters in the finish word.
Java code:

public class StartFinish {
	private static String start = "cat";
	private static String finish = "hat";
	public static void main(String[] args) {
		System.out.println(findMinimumSteps(start, finish));
	}
	
	public static int findMinimumSteps(String start, String finish) {
		int j = 0;
		int cnt = 0;
		for(int i = 0; i < start.length(); i++) {
			if(start.charAt(i) != finish.charAt(j)) {
				cnt++;
			}
			j++;
		}
		return cnt;
	}

}

In question it is written in minimum steps

I think there is no need of graph or tree. The question is asking minimum no of steps which is in worst case will be 3(three letter words: three bits to flip). Simple loop should work.

Suggestion and corrections welcomed :)

public class ChangeWord {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// cat -> dog : dat -> dot -> dog;
		int steps = findMinimumStepsToChange("cat", "dog");
		System.out.println(steps);
		// pic -> cat : pic -> cic -> cac -> cat
		int steps2 = findMinimumStepsToChange("pic", "cat");
		System.out.println(steps2);

	}
	
	
	public static int findMinimumStepsToChange(String word1, String word2){
		if("".equals(word1)||"".equals(word2))
			return -1;
		if(word1.equals(word2))return 0;
		
		int steps = 0;
		int charCount = 0;
		
		for(int i=0;i<word1.length();i++){
			
			if(word1.charAt(i) != word2.charAt(i)){
				
				steps++;
			}
		}
		
		return steps;
	}

}