Databases
StackOverflow2013
Postsdbo
PO[Interview]Similar Words Distance Calculation
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO[Interview]Similar Words Distance Calculation
    text
    copied!<p>This Question was asked in an interview</p> <blockquote> <p>Assume you have a dictionary of words: (use if you have /usr/share/dict/words).</p> <p>Given a word(eg: cricket), give me all the words from the dictionary that could be reached by doing n operations. Where an operation is one of :<br> Addition<br> Replace<br> Deletion</p> </blockquote> <p>For example lets find all the words that can be formed from "cricket" if only 1 operation is allowed.</p> <p>{'word': 'clicket', 'op': ['replace']} {'word': 'crickey', 'op': ['replace']} {'word': 'crickety', 'op': ['addition']} etc</p> <p>I am printing in my own format, but you get the gist. </p> <p>Here is what I have attempted </p> <ol> <li>based on number of operations compute a list of all possible sequence. </li> <li>then iterate over the list and apply them one by one and store words which are present in dictionary.</li> </ol> <p>This is brute force solution. I am wondering if there is an efficient solution for this. Below is the code for brute force solution</p> <pre><code>import java.io.BufferedReader; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; public class SimilarWordDistance { Map&lt;String,Boolean&gt; dictionary = new HashMap&lt;String,Boolean&gt;(); int ADDTION = -1; int REPLACE = 0; int DELETION = 1; /** * @param args * @throws IOException */ public static void main(String[] args) throws IOException { SimilarWordDistance swd = new SimilarWordDistance(); swd.readDictionary(); //swd.findSimilar("cricket", 1); swd.findSimilar("happiness", 3); } public void findSimilar(String word,int num) { int possibleOperations = (int) Math.pow(3 , num); Integer[][] operations = new Integer[possibleOperations][num]; buildOperationsArray(num, possibleOperations, operations); List&lt;String&gt; l = new ArrayList&lt;String&gt;(); l.add(word); Map&lt;String,Integer[]&gt; sols = new HashMap&lt;String,Integer[]&gt;(); for(int i=0;i&lt;operations.length;i++) applyOperation(operations[i],l,sols); Iterator&lt;String&gt; itr = sols.keySet().iterator(); while(itr.hasNext()) { String n = itr.next(); printSolution(sols.get(n), n); } } private void applyOperation(Integer[] operation,List&lt;String&gt; word,Map&lt;String,Integer[]&gt; sols) { List&lt;String&gt; possiblities = word; for(int i=0;i&lt;operation.length;i++) { if(operation[i] == ADDTION) { List&lt;String&gt; temp = new ArrayList&lt;String&gt;(); for(int j =0;j&lt;possiblities.size();j++) { temp.addAll(applyAdditionOperation(possiblities.get(j))); //System.out.println(temp.size()); } possiblities = temp; } if(operation[i] == REPLACE) { List&lt;String&gt; temp = new ArrayList&lt;String&gt;(); for(int j =0;j&lt;possiblities.size();j++) { temp.addAll(applyReplace(possiblities.get(j))); //System.out.println(temp.size()); } possiblities = temp; } if(operation[i] == DELETION) { List&lt;String&gt; temp = new ArrayList&lt;String&gt;(); for(int j =0;j&lt;possiblities.size();j++) { temp.addAll(applyDeletion(possiblities.get(j))); } possiblities = temp; } } for(int i=0;i&lt;possiblities.size() ;i++) { String w = possiblities.get(i); if(dictionary.containsKey(w)) { sols.put(w, operation); } } } protected void printSolution(Integer[] operation, String w) { System.out.print(w+"\t" ); for(int j=0;j&lt;operation.length;j++) { System.out.print(printOperation(operation[j])+"\t"); } System.out.println(); } private String printOperation(Integer integer) { if(integer == ADDTION) { return "Addition"; } if(integer == REPLACE) { return "Replace"; } else { return "Deletion"; } } private List&lt;String&gt; applyAdditionOperation(String word) { char[] possiblities = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','y','z'}; List&lt;String&gt; possibleWords = new ArrayList&lt;String&gt;(); for(int i=0;i&lt;possiblities.length;i++) { for(int j=0;j&lt;word.length();j++) { String temp = insertAt(word,j,possiblities[i]); possibleWords.add(temp); } } return possibleWords; } private List&lt;String&gt; applyDeletion(String word) { List&lt;String&gt; possibleWord = new ArrayList&lt;String&gt;(); for(int i=0;i&lt;word.length();i++) { String prefix = word.substring(0,i); String suffix = word.substring(i+1,word.length()); String tenp = prefix+suffix; possibleWord.add(tenp); } return possibleWord; } private List&lt;String&gt; applyReplace(String word) { char[] possiblities = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','y','z'}; List&lt;String&gt; possibleWord = new ArrayList&lt;String&gt;(); for(int i=0;i&lt;possiblities.length;i++) { for(int j=0;j&lt;word.length();j++) { String temp = word.substring(0,j)+possiblities[i]+word.substring(j+1,word.length()); if(temp.length()!=word.length()) System.out.println("#####################"); possibleWord.add(temp); } } return possibleWord; } private String insertAt(String word, int j, char c) { String prefix = word.substring(0,j); String suffix = word.substring(j+1,word.length()); String ret = prefix+c+suffix; return ret; } protected void buildOperationsArray(int num, int possibleOperations, Integer[][] operations) { for(int i=0;i&lt;possibleOperations;i=i+9){ for(int j=0;j&lt;num;j++) { fillPossiblities(num, operations, ADDTION, i, j); // 3 rows if(i+3&lt;possibleOperations) fillPossiblities(num, operations, REPLACE, i+3, j); // 3 rows if(i+6 &lt; possibleOperations) fillPossiblities(num, operations, DELETION, i+6, j); // 3 rows } } /* System.out.println(operations.length); for(int i=0;i&lt;operations.length;i++) { for(int j=0;j&lt;operations[0].length;j++) { System.out.print(operations[i][j]+"\t"); } System.out.println(); }*/ } /** * Every time this method is called it will fill all the colums of the passed row * with 1 default value and the fill the next 2 rows with possible permutation of that * column * @param num * @param operations * @param def * @param curRow */ protected void fillPossiblities(int num, Integer[][] operations,int def,int curRow,int curColumn) { for(int i=0;i&lt;num;i++) { operations[curRow][i] = def; } for(int i=0;i&lt;num;i++) { if(i!=curColumn) operations[curRow+1][i] = def; } operations[curRow+1][curColumn] = getNext(def); // int def1 = getNext(def); for(int i=0;i&lt;num;i++) { if(i!=curColumn) operations[curRow+2][i] = def; } operations[curRow+2][curColumn] = getNext(def1); } private int getNext(int def) { if(def == -1) { return REPLACE; } if(def == 0) { return DELETION; } else { return ADDTION; } } public void readDictionary() throws IOException { BufferedReader in = new BufferedReader(new FileReader("C:\\Documents\\Downloads\\words")); while (in.ready()) { String s = in.readLine(); dictionary.put(s, true); } in.close(); } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload