Lil' preparation before the interview. This is my solution to the problem in title. The code is pretty straight forward. Requesting suggestions for improvement and also verification of complexity, which I guess is O(26n)
public class CatToDog {
static Set<String> dictionary;
static {
dictionary = new HashSet<String>();
dictionary.add("camera");
dictionary.add("cat");
dictionary.add("cot");
dictionary.add("cot");
dictionary.add("dome");
dictionary.add("dot");
dictionary.add("dog");
// dictionary = new TreeSet<String>();
// BufferedReader br = null;
// try {
// try {
// br = new BufferedReader(new FileReader("/Users/ameya.patil/Desktop/text.txt"));
// String line;
// while ((line = br.readLine()) != null) {
// dictionary.add(line.split(":")[0]);
// }
//
// } finally {
// br.close();
// }
// } catch (Exception e) {
// throw new RuntimeException("Error while reading dictionary");
// }
}
private CatToDog () { };
public static List<String> listWords(String startWord, String endWord) {
final Queue<String> queue = new LinkedList<String>();
final Map<String, String> backTrack = new HashMap<String, String>();
queue.add(startWord);
backTrack.put(startWord, null);
while (!queue.isEmpty()) {
String currentWord = queue.poll();
if (currentWord.equals(endWord)) {
return mapToList(backTrack, endWord);
}
addValidOneChangeWords(currentWord, queue, backTrack);
}
return Collections.EMPTY_LIST;
}
private static void addValidOneChangeWords(String startWord, Queue<String> queue, Map<String, String> backTrack) {
for (int i = 0; i < startWord.length(); i++) {
char[] endWord = startWord.toCharArray();
for (char ch = 'a'; ch < 'z'; ch++) {
endWord[i] = ch;
String word = new String(endWord);
if (validate(word, backTrack, startWord)) {
queue.add(word);
backTrack.put(word, startWord);
}
}
}
}
private static boolean validate(String word, Map<String, String> backTrack, String startWord) {
return dictionary.contains(word) && !backTrack.containsKey(word) && !word.equals(startWord);
}
private static List<String> mapToList (Map<String, String> backTrack, String endWord) {
final List<String> wordList = new ArrayList<String>();
String word = endWord;
while (backTrack.containsKey(word)) {
wordList.add(word);
word = backTrack.get(word);
}
Collections.reverse(wordList);
return wordList;
}
public static void main(String[] args) {
for (String string : listWords("cat", "dog")) {
System.out.println(string);
}
}
}
v
tow
, can't you first iterate both in parallel (until the end of either word was hit) and increase the distance by 1 for every character which is not the same at the current position in both strings? At the end, just add the difference in length to the distance. I.e. the difference betweencamera
andcat
would be 4, the difference betweencat
anddog
would be 3, betweendot
anddog
just 1. That would be O(n). \$\endgroup\$ – Frerich Raabe Dec 2 '13 at 11:41