Data Structures and Performance | Week 6

Course Name: Data Structures and Performance

Course Link: Data Structures and Performance

These are Data Structures and Performance Week 6 Coursera Answers

Programming Assignment: Spelling Suggestions

Steps: Create two java files of same name NearbyWords.java, one for column one i.e., Mutations and another for column second i.e., Suggestions and upload in respective columns.

Mutations(NearbyWords.java):

package spelling;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class NearbyWords implements SpellingSuggest {
  private static final int THRESHOLD = 1000; 

  Dictionary dict;

  public NearbyWords (Dictionary dict) 
  {
    this.dict = dict;
  }

  public List<String> distanceOne(String s, boolean wordsOnly )  {
       List<String> retList = new ArrayList<String>();
       insertions(s, retList, wordsOnly);
       substitution(s, retList, wordsOnly);
       deletions(s, retList, wordsOnly);
       return retList;
  }

  public void substitution(String s, List<String> currentList, boolean wordsOnly) {
    for(int index = 0; index < s.length(); index++){
      for(int charCode = (int)'a'; charCode <= (int)'z'; charCode++) {
        StringBuffer sb = new StringBuffer(s);
        sb.setCharAt(index, (char)charCode);
        if(!currentList.contains(sb.toString()) && 
            (!wordsOnly||dict.isWord(sb.toString())) &&
            !s.equals(sb.toString())) {
          currentList.add(sb.toString());
        }
      }
    }
  }

  public void insertions(String s, List<String> currentList, boolean wordsOnly ) {
    for(int index = 0; index < s.length() + 1; index++){
      for(int charCode = (int)'a'; charCode <= (int)'z'; charCode++) {
        String[] strs = s.split("");
        LinkedList<String> sList = new LinkedList(Arrays.asList(strs));
        sList.add(index,  Character.toString((char)charCode));
        String newWord = listToString(sList);
        if(!currentList.contains(newWord) && 
            (!wordsOnly||dict.isWord(newWord)) &&
            !s.equals(newWord)) {
          currentList.add(newWord);
        }
      }
    }
  }

  private String listToString(List<String> list) {
    String ret = "";
    for(String c: list) {
      ret += c;
    }
    return ret;
  }

  public void deletions(String s, List<String> currentList, boolean wordsOnly ) {
    for(int index = 0; index < s.length(); index++){
      String[] strs = s.split("");
      LinkedList<String> sList = new LinkedList(Arrays.asList(strs));
      sList.remove(index);
      String newWord = listToString(sList);
      if(!currentList.contains(newWord) && 
          (!wordsOnly||dict.isWord(newWord)) &&
          !s.equals(newWord)) {
        currentList.add(newWord);
      }
    }
  }

  @Override
  public List<String> suggestions(String word, int numSuggestions) {
    List<String> queue = new LinkedList<String>();
    HashSet<String> visited = new HashSet<String>();
    List<String> retList = new LinkedList<String>();
    queue.add(word);
    String curWord = queue.remove(0);
    while(curWord != null && retList.size() < numSuggestions) {
      if(visited.contains(curWord)) {
        curWord = queue.remove(0);
      } else {
        visited.add(curWord);
        List<String> words = distanceOne(curWord, true);
        retList.addAll(words);
        queue.addAll(words);
        curWord = queue.remove(0);
      }
    }
    return retList.subList(0, numSuggestions);
  }  

   public static void main(String[] args) {
     String word = "i";
     Dictionary d = new DictionaryHashSet();
     DictionaryLoader.loadDictionary(d, "data/dict.txt");
     NearbyWords w = new NearbyWords(d);
     List<String> l = w.distanceOne(word, true);
     System.out.println("One away word Strings for for \""+word+"\" are:");
     System.out.println(l+"\n");

     word = "tailo";
     List<String> suggest = w.suggestions(word, 10);
     System.out.println("Spelling Suggestions for \""+word+"\" are:");
     System.out.println(suggest);
   }
}