CareerCup

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
		static Map<String, Integer> map = new HashMap<String, Integer> ();
	static int f (String s, String d, int count) {
		if (s == null) {
			return Integer.MAX_VALUE;
		}
		if (map.containsKey(s)) {
			return map.get(s);
		}
		if (s.equals(d)) {
			return count;
		}
		map.put (s, Integer.MAX_VALUE);
		int min = minimunOf (
				f(rule1(s), d, count+1),
				f(rule2(s), d, count+1),
				f(rule3(s), d, count+1),
				f(rule4(s), d, count+1)
				);
		map.put(s, min);
		return min;
	}

	private static int minimunOf(int... n) {
		ArrayList<Integer> list = new ArrayList<Integer> ();
		for (int i: n) {
			list.add(i);
		}
		Integer [] in = list.toArray(new Integer[0]);
		Arrays.sort(in);
		return in[0];
	}

	private static String rule1(String s) {
		int i = s.indexOf('_');
		if (i == s.length()-1) {
			return null;
		}
		char[] temp = s.toCharArray();
		temp[i] = temp[i+1];
		temp[i+1] = '_';
		return new String (temp);
	}

	private static String rule2(String s) {
		int i = s.indexOf('_');
		if (i == 0) {
			return null;
		}
		char[] temp = s.toCharArray();
		temp[i] = temp[i-1];
		temp[i-1] = '_';
		return new String (temp);
	}
	
	private static String rule3(String s) {
		int i = s.indexOf('_');
		if (i == s.length()-1 || i == s.length()-2 ) {
			return null;
		}
		char[] temp = s.toCharArray();
		if (temp[i+1] == temp[i+2]) {
			return null;
		}
		temp[i] = temp[i+2];
		temp[i+2] = '_';
		return new String (temp);
	}
	
	private static String rule4(String s) {
		int i = s.indexOf('_');
		if (i == 0 || i == 1 ) {
			return null;
		}
		char[] temp = s.toCharArray();
		if (temp[i-1] == temp[i-2]) {
			return null;
		}
		temp[i] = temp[i-2];
		temp[i-2] = '_';
		return new String (temp);
	}
	
	public static void main(String[] args) {
		String s = "abaa_a";
		String d = "b_aaaa";
		
		String[][] input = {
				{"abaa_a", "b_aaaa"},
				{"abc_abc", "abca_bc"},
				{"abc_abc", "abc_bac"},
				{"abc_abc", "ab_cabc"},
				{"abc_abc", "abc_abc"},
				{"abc_abc", "abcabc"},
		};
		
		for (int i = 0; i < input.length; i++) {
			map.clear();
			int min = f (input[i][0], input[i][1], 0);
			if (min == Integer.MAX_VALUE)
				System.out.println("No Result");
			else
				System.out.println("Result: " + min);
		}
	}
}

but this is a very inefficient process for both time and space ?? what will be complexity of your program, can you please confirm ?

This is a common kind of search in artificial intelligence. The time complexity is the same as DFS, O(b^h), where b is the branching factor (4 in this case = number of rules), and h is the height of the state space tree (edit distance between input and output).

In memory, it's also O(b^h). It can be problematic if we deal with large strings, however I believe it's worthy since we have the minimum number of steps by the first time we arrive at the output, as opposed to other kinds of search.

Furthermore, there is one question in the book about transforming one word into another by using only intermediary words that exist in the dictionary. The solution for that problem is very similar.

@Victor cant it help us that there are only 'a' and 'b' . Your algorithm is a general.

I believe having only two characters doesn't make difference really. But I could be wrong.

Victor, but the problem in the CtCI book about transforming one word into another using only words in the dictionary doesn't have exponential.complexity, because the total number of dictionary words is very limited!