Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
I think this is a graph problem.
Construction of graph involves, connecting all words that vary by a distance of one.
Then the problem is reachability from one vertex to another.
Here's a python implementation. Assuming that the source word and destination word needn't be of the same size, transformation could involve (+) adding / (-) removing a character from the word for the transformation too.
Considering all the words in the dictionary to be nodes in a graph, process the whole dictionary once and create the graph. Then given two words initiate a BFS from source to destination and we'll have the shortest chain of transformations required.
In the worst case, we might have to traverse the whole graph to find a transformation or a transformation may not exist at all. This function returns the list / array of the transformation strings, using len(returnedArray) we can get the required result.
import os
import collections
import string
def constructGraph(dictionary):
graph=collections.defaultdict(list)
letters=string.lowercase
for word in dictionary:
for i in range(len(word)):
remove=word[:i]+word[i+1:]
if remove in dictionary:
graph[word].append(remove)
for char in letters:
change=word[:i]+char+word[i+1:]
if change in dictionary and change!=word:
graph[word].append(change)
for i in range(len(word)+1):
for char in letters:
add=word[:i]+char+word[i:]
if add in dictionary:
graph[word].append(add)
return graph
def transformWord(graph, start, goal):
paths=collections.deque([ [start] ])
extended=set()
#Breadth First Search
while len(paths)!=0:
currentPath=paths.popleft()
currentWord=currentPath[-1]
if currentWord==goal:
return currentPath
elif currentWord in extended:
continue
extended.add(currentWord)
transforms=graph[currentWord]
for word in transforms:
if word not in currentPath:
paths.append(currentPath[:]+[word])
return []
dictionary = ['cat', 'bat', 'bet', 'bed', 'at', 'ad', 'ed', 'cat', 'cog', 'dog', 'cot'] #Complete dictionary passed here.
graph = constructGraph(dictionary) # Constructing the graph
print len(transformWord(graph, 'bat' , 'bed')) # Transform word and return []; find its length using len()
print len(transformWord(graph, 'bat' , 'cat'))
print len(transformWord(graph, 'cat' , 'bet'))
print len(transformWord(graph, 'cat' , 'dog'))
print len(transformWord(graph, 'bat' , 'hat'))
One problem with this is that if there's no transformation it returns an empty transformation list [ ] and the len([ ]) is 0, but rather has to be shown as null, a simple if statement would resolve this.
I did not check for all the possibilities but here is the code in python. I am assuming a predefined dictionary is present.
def indict(word):
diction = ['cat', 'bat', 'bet', 'bed', 'at', 'ad', 'ed', 'cat', 'cog', 'dog', 'cot']
if word in diction:
return True
else:
return False
def stepschange(word1, word2):
if not (len(word1)!= len(word2)) and indict(word1) and indict(word2):
breaking1 = [i for i in word1]
counter =0
for j in word2:
if j in breaking1:
counter = counter +1
return 1+len(word1)-counter
else:
return 0
print stepschange('bat' , 'bed'),"11"
print stepschange('bat' , 'cat'),"11"
print stepschange('cat' , 'bet'),"11"
print stepschange('cat' , 'bog'),"11"
@Test
public void testDictionary() {
// Turn cat into dog
dictionary.add("cat");
dictionary.add("cot");
dictionary.add("dot");
dictionary.add("cog");
dictionary.add("dog");
convert("cat", "dog");
}
public static List<String> dictionary = new LinkedList<>();
public String convert(String changing, String end) {
if (changing.equals(end)) return end;
int i = 0;
for (char c : end.toCharArray()) {
char[] changingArray = changing.toCharArray();
if (changingArray[i] != c) {
changingArray[i] = c;
if (dictionary.contains(new String(changingArray))) {
System.out.println(new String(changingArray));
return convert(new String(changingArray), end);
}
}
i++;
}
return "impossible";
}
Store the dictionary as a graph. Have it set up so that you have vertices with labels 1, 2, 3, etc (these represent the number of letters in the word). From each of these, create complete-subgraphs, where every node (representing a word) with n characters, is connected to every other node with n characters. Every edge from a node is given by the letter that is changed, and the position of that new character.
Assume your classes appear as follows:
public class Vertex {
// Adjacency list, where the key is the index of the letter to change, and the value is
// another map, where the key is the character to change, and the value is the
// vertex of the new word
Hashmap<Integer, Hashmap<Character, Vertex>> adj =
new Hashmap<Integer, Hashmap<Character, Vertex>>();
String data;
public Vertex getAdjacentVertex(int index, char letter) {
if (!adj.containsKey(index))
return null;
return ajd.get(index).get(letter);
}
}
Then you can find the number of steps it takes to get there with the following:
public Integer numSteps(Vertex word, String target) {
if (word == null) return null;
if word.data.equals(target) return 0;
Map<Integer, Character> wordMap = new HashMap<Integer, Character>();
for (int i = 0; i < target.length(); i++) {
wordMap.put(i, target.charAt(i));
}
int numSteps = 0;
while (!wordMap.empty() && !target.equals(word.data)) {
Iterator<Integer> wordKeys = wordMap.keySet().iterator();
boolean foundEdge = false;
while (wordKeys.hasNext()) {
Integer wordKey = wordKeys.next();
if (word.getAdjacentVertex(wordKey, wordMap.get(wordKey)) != null) {
word = word.getAdjacentVertex(wordKey, wordMap.get(wordKey));
wordMap.remove(wordKey);
foundEdge = true;
numSteps++;
break;
}
}
if (!foundEdge)
return null;
}
return numSteps;
}
This solution would run in O(n) time, but use O(n^2) space.
//Solution with Dynamic programming, although, haven't even compiled, idea is like, if replacing one character results into a valid word in dictionary then its a similar sub-problem like what's the minimum iterations required from that point onwards.
findMinWays(string str)
{
if (str == endWord) {
return 0;
}
int min=MAX_INT, num=0;
for (int i=0; i<str.length-1; i++) {
if ( dict.exists( str.replace(i, endWord[i]) ) ) {
num = findMinWays(str.replace(i, endWord[i]));
if (num < min)
min = num;
}
}
if (min==MAX_INT)
return 0;
return min;
}
Do breath first search. Space required is upper bounded by dictionary size. Same for time if we consider inner two loops 'constant' because of 26 letters and maximum length word :)
import string
def dict_distance(dict, source_word, target_word):
processed = {}
horizon = {source_word:0}
keep_going = True
while keep_going:
new_horizon = {}
for key, value in horizon.iteritems():
if key == target_word:
return value
else:
processed[key] = value
for char in string.ascii_lowercase:
for idx in range(0,len(key)):
new_word = key[:idx] + char + key[idx+1:]
if new_word in dict and new_word not in processed and new_word not in new_horizon:
new_horizon[new_word] = value + 1
keep_going = len(new_horizon) > 0
horizon = new_horizon
return None
public class TransformWithDictionary {
public static Integer getMinTransformations(String[] dictionary, String start, String end) {
// Construct Map of words to a Set of their adjacent words in the dictionary
Map<String, Set<String>> adjacent = new HashMap<>();
for (String s : dictionary) {
Set<String> adjacentWords = new HashSet<>();
for (String s2 : dictionary) {
if (s == s2) continue;
if (isOneEditAway(s, s2)) adjacentWords.add(s2);
}
adjacent.put(s, adjacentWords);
}
return getMinTransformations(adjacent, start, end, null, 0);
}
/**
* Checks if start can be transformed into end by changing no more than one letter
*/
public static boolean isOneEditAway(String start, String end) {
if (start == null || end == null) return false;
int edits = 0;
int index = 0;
while (edits < 2 && index < end.length()) {
if (start.charAt(index) != end.charAt(index)) edits++;
index++;
}
return edits == 1;
}
public static Integer getMinTransformations(Map<String, Set<String>> dictionary, String start, String end,
Integer min, int steps) {
if (min != null && steps == min) return null; // This path is already longer than the min, just return null
Set<String> adjacentWords = dictionary.get(start);
if (adjacentWords == null) return null; // No adjacent words remaining, return null
if (adjacentWords.contains(end)) return 1; // Base case
// Remove the current word from dictionary to prevent an endless loop
dictionary.remove(start);
// Loop through adjacent words looking for min transformation steps
for (String word : adjacentWords) {
Integer result = getMinTransformations(dictionary, word, end, min, steps + 1);
if (result != null) {
min = min == null ? result + 1 : Math.min(min, result + 1);
}
}
// Finally, return the minimum number of transformations we found
return min;
}
public static void main(String[] args) {
String[] dictionary = new String[] {
"cat", "dog", "pog", "bog", "cot", "all", "yew", "nit", "cog", "raw", "sew", "mow", "saw", "was", "pam",
"sam", "lit", "bit", "wit", "vim", "war", "rat", "mat", "log", "cow", "paw" };
System.out.println("pog -> dog = " + getMinTransformations(dictionary, "pog", "dog")); // 1
System.out.println("pam -> saw = " + getMinTransformations(dictionary, "pam", "saw")); // 2
System.out.println("cat -> dog = " + getMinTransformations(dictionary, "cat", "dog")); // 3
System.out.println("sam -> lit = " + getMinTransformations(dictionary, "sam", "lit")); // null
}
}
sorry for the fancy dictionary!
class WordTransform {
static def dictionary = ["black", "browk", "brown", "blowk", "block", "white"]
static void main(String... args) {
println iterationsToTransform("brown", "black")
println iterationsToTransform("white", "black")
}
static Integer iterationsToTransform(String from, String to) {
if (from && to && from.length() == to.length()
&& dictionary.contains(to)) {
int iterations = 0
int index = 0
while (!from.equals(to) && index < from.size()) {
def word = tryToReplace(from, to, index++)
if (word != from) {
iterations++
index = 0
}
from = word
}
if (from.equals(to))
iterations
}
else null
}
static String tryToReplace(String from, String to, int index) {
def word = from.replace(from.charAt(index), to.charAt(index))
dictionary.contains(word) ? word : from
}
}
c# implementation.
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MinimumNumberOfTransformations {
using Graph = Dictionary<string, HashSet<string>>;
public static class WordsTransformer {
//implements BFS
public static string GetMinNumOfTransformations( string startWord, string endWord ) {
// perform here all necessary checks: the words' lengths must be equal, etc...
_startWord = startWord;
_endWord = endWord;
_graph = new Graph();
_counter = 0;
var frontier = new HashSet<string> { _startWord };
while ( frontier.Count != 0 ) {
_counter++;
var tmpHashSet = new HashSet<string>();
foreach ( var word in frontier ) {
//add node
_graph.Add( word, new HashSet<string>() );
//add its descendants
var res = AddDescendants( word );
// if endWord is among descendants - return
if ( res != null ) { return res; }
tmpHashSet.UnionWith( _graph[ word ] );
}
frontier = tmpHashSet;
}
return null;
}
private static string AddDescendants( string word ) {
for ( int i = 0; i < word.Length; i++ ) {
var wordAsCharArr = word.ToCharArray();
foreach ( var ch in Alphabet ) {
wordAsCharArr[ i ] = ch;
var newWord = wordAsCharArr.RestoreString();
AddNewWord( word, newWord );
// if endWord is among descendants of "word" - return
if ( newWord == _endWord ) {
return BuildUpPathAndNumOfSteps( word );
}
}
}
return null;
}
private static string BuildUpPathAndNumOfSteps( string word ) {
string path = word + "->" + _endWord;
var curr = word;
for ( int j = 0; j < _counter-1; j++ ) {
var kvp = _graph.FirstOrDefault( x => x.Value.Contains( curr ) );
curr = kvp.Key;
path = curr + "->" + path;
}
return _counter + ", " + path;
}
private static void AddNewWord( string key, string newWord ) {
if ( Dictionary.Contains( newWord ) &&
!_graph.Values.Any( x => x.Contains( newWord ) ) &&
!_graph.Keys.Any( y => y.Contains( newWord ) ) )
{
_graph[ key ].Add( newWord );
}
}
static string RestoreString( this IEnumerable<char> arr ) {
var chArr = arr.ToArray();
var sb = new StringBuilder();
for( int i = 0; i < chArr.Length; i++ ) {
sb.Append( chArr[ i ] );
}
return sb.ToString();
}
static readonly List<string> Dictionary = new List<string> {
"cot","cog", "sat","sad","car","bar","bag","cab","rat","ray","say","cat", "dog", // etc...
"cut", "cug"
};
static readonly List<char> Alphabet = new List<char> {
'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','r','s','t','u','v','w','x','y','z'
};
private static string _startWord;
private static string _endWord;
private static Graph _graph;
private static int _counter;
}
}
<?php
$dictionary = ['cap', 'cup', 'cod', 'fog', 'cut', 'hut', 'hot', 'hit', 'cat', 'cot', 'cog', 'dog'];
$results = search($dictionary, 'cat', 'dog');
var_dump($results);
/**
* @param string[] $dictionary
* @param string $start
* @param string $end
*
* @return int|null
*/
function search(array $dictionary, $start, $end)
{
$graph = prepareGraph($dictionary);
$path[$start] = [$start];
$queue[] = $start;
while($queue) {
$currentWord = current($queue);
$currentPath = $path[$currentWord];
if ($end === $currentWord) {
return count($currentPath) - 1;
}
if (false === isset($graph[$currentWord])) {
return null;
}
foreach($graph[$currentWord] as $nextWord) {
if (array_key_exists($nextWord, $path)) {
continue;
}
$queue[] = $nextWord;
$path[$nextWord] = array_merge($currentPath, [$nextWord]);
}
next($queue);
}
}
/**
* @param string[] $dictionary
*
* @return array
*/
function prepareGraph(array $dictionary)
{
$dictionary = array_map('str_split', $dictionary);
$result = [];
foreach ($dictionary as $word1) {
foreach ($dictionary as $word2) {
if (1 === count(array_diff_assoc($word1, $word2))) {
$result[implode('', $word1)][] = implode('', $word2);
}
}
}
return $result;
}
JavaScript solution:
function getMinimumChanges(start, end, dictionary) {
var matchingChars;
var charsThatMatchEnd;
var newWordindex;
var newWordDistance;
var currentWord = start;
var count = 0;
dictionary = dictionary.filter(function(val, index, array) {
return getNumberOfMatchingChars(val, start) > 0 && getNumberOfMatchingChars(val, end) > 0;
});
// Add the end word to the dictionary
dictionary.push(end);
while (dictionary.length > 0 && currentWord !== end) {
count ++;
newWordCharsThatMatchEnd = 0;
newWordindex = -1;
dictionary.map(function (val, index) {
matchingChars = getNumberOfMatchingChars(val, currentWord);
if (matchingChars !== (start.length - 1)) {
// More than 1 char away so we can't use this
return;
}
// get the item closest to the end word from the dictionary
charsThatMatchEnd = getNumberOfMatchingChars(val, end);
if (charsThatMatchEnd > newWordCharsThatMatchEnd) {
newWordCharsThatMatchEnd = charsThatMatchEnd;
newWordindex = index;
}
});
if (newWordindex === -1) {
// There is no way to get to the end
return null;
}
currentWord = dictionary[newWordindex];
// remove the word from the dictionary so we don't get into a loop
dictionary.splice(newWordindex, 1);
}
function getNumberOfMatchingChars (first, second) {
var i;
var matchingIndex;
var matchingChars = 0;
for (i = 0; i < first.length; i++) {
matchingIndex = second.indexOf(first[i]);
if (matchingIndex === -1) {
continue;
}
matchingChars += 1;
}
return matchingChars;
}
return count;
}
This can be solved two ways:
BFS solution using backtracking HashMap:
Or using recursive DFS, the benefit of this is that we can utilise the recursion stack to do the backtracking:
- Coder May 03, 2016