Google – Correct Misspelling

Google – Correct Misspelling
Given a dictionary and a misspelling word with only ONE misspelled character, correct it.
Ex: [apple, people, …], adple => apple
[Solution]
[Solution #1] Brute Force
Compare the misspelled word with every word in the dictionary.
time: O(n * Avg(len))
[Solution #2] One Edit Distance
Do one edit distance on every word in the dict with the misspelled word
其实就是Solution #1
time: O(n * Avg(len))
[Solution #3] Trie tree with k tolerant
这个没有具体实现，不过这种思想倒是没见过，其他题目或许可以借鉴。
思路就是对dict建trie tree，然后对misspelled word做dfs search, 不同于普通的trie tree搜索，这里可以设置一个容忍度，比如这题可以设为1，如果搜索过程中有1个character不同，可以继续往下搜索，而不是直接return。
不过这样的做法对于这道题而言时间复杂度并没有提升，依然是O(n * Avg(len))
[Solution #4] backtracking
因为每个character只有26种可能性，对Misspelled word的每个character尝试所有可能性看有没有一种可能性在dictionary里就可以了。
time: O(len * 26)
下面的code是backtracking的做法。

  public List<String> correctWord(String[] dict, String word) {

    List<String> result = new ArrayList<>();

    if (dict == null || dict.length == 0 || word == null) {

      return result;

    }

 

    Set<String> set = new HashSet<>();

    for (String s : dict) {

      set.add(s);

    }

 

    char[] ch = word.toCharArray();

    for (int i = 0; i < ch.length; i++) {

      char save = ch[i];

      for (char c = 'a'; c <= 'z'; c++) {

        if (c != ch[i]) {

          ch[i] = c;

          String newStr = new String(ch);

          if (set.contains(newStr)) {

            result.add(newStr);

          }

        }

      }

      ch[i] = save;

    }

 

    return result;

  }

Read full article from Google – Correct Misspelling