Case study: Word ladder - find all paths

Oct. 26, 2019

Introduction

It was my mock interview at 10:00 PM on Oct. 25, 2019. The interviewee is very experienced engineer, with Google onsite and coming Facebook onsite interview. I like to learn how she wrote the algorithm bug free, and also I like to learn how she trains herself using Leetcode.com. She only solved around 200 algorithms on leetcode.com.

Case study

I like to write the idea using C# as well later. Here is the transcript with the code.

	import java.io.*;
	import java.util.*;
	/*
	* To execute Java, please define "static void main" on a class
	* named Solution.
	*
	* If you need more classes, simply define them inline.
	*/
	class Solution {
	public static void main(String[] args) {
	String[] words = {"bood", "beod", "besd","goot","gost","gest","best"};
	List<String> res = findPaths("good", "best", words);
	for(String s : res) {
	System.out.println(s);
	}
	}
	public static List<String> findPaths(String src, String dest, String[] words) {
	List<String> res = new ArrayList<>();
	int[] visited = new int[words.length];
	dfs(src, dest, words, visited, "", res);
	return res;
	}
	public static void dfs(String src, String dest, String[] words, int[] visited, String prefix, List<String> res) {
	if(src.equals(dest)) {
	res.add(prefix + "->" + dest);
	return;
	}
	for(int i=0; i<words.length; i++) { // search one hop away - good -> maximum number of dictionary - distinct words with len = 4
	if(visited[i] == 0) {
	visited[i] = 1;
	if(isNext(src, words[i])) {
	//if(prefix.length() == 0)
	String pre = prefix + "->" + src;
	dfs(words[i], dest, words, visited, pre, res);
	}
	visited[i] = 0;
	}
	}
	}
	public static boolean isNext(String src, String dest) { // only one char is different
	boolean isOneChar = false;
	for(int i=0; i<src.length(); i++) {
	if(src.charAt(i) == dest.charAt(i)) continue;
	if(isOneChar == true) return false; // second char is found
	isOneChar = true;
	}
	return isOneChar;
	}
	}
	/*
	source = "good";
	dest = "best";
	var words = new string[] {"bood", "beod", "besd","goot","gost","gest","best"};
	// good, bood, food, mood, wood, hood - by each char 26 * 4 = 100, 26 * 26 * 26 * 26 = 100 * 100 * 100 * 100 = 10^8
	// good -> index = 0 a - z -> try 26 * 4 to find all
	// brute force -> dictionary 10^8
	two paths
	good->bood->beod->besd->best
	good->goot->gost->gest->best
	Given a start and destination word, a list of words as a dictionary, find all paths from source to dest word, each intermediate word should be in dictionary. Each time one char is updated.
	*/

view raw WordLadder_FindAllPaths.Java hosted with ❤ by GitHub