5

给定一个长度为l的正确单词列表和一个长度l为 的不正确单词列表，通过交换两个连续字母，找到与正确单词列表不同的错误单词列表中的单词。这些词被认为是错别字。例如，hte被认为是拼写错误的thewhilehet不被视为拼写错误。

什么是最省时的算法，可以让我们找到这个定义被认为是拼写错误的单词列表？

我被告知该列表可以在线性时间内计算，但我无法在线性时间内找到解决方案。我能想到的唯一方法是将一个列表中的所有字母与另一个列表进行比较。

4

4 回答 4

4 
L - list of correct words of size n.
L'- list of incorrect words of size m.
H - hash table
R - result set

1. for each word w in L :
   1.1  for each typo t of w : //there are l-1 typos
     1.1.1 insert t into H
2. for each word w' in L' :
   2.1 if w' in H insert w' in R
3. return R

时间复杂度： O(n*l)+O(m) = O(max(n*l,m))

空间复杂度： O(n*l)

于 2012-10-21T05:23:54.570 回答
0

假设每个“拼写错误”的单词中只能有一个交换：

从一个空的 HashTable H 开始。

对于 INCORRECT 单词列表中的每个单词 K：

  • 通过交换每对连续字符来生成 (l-1) 个新单词：K_1, K_2, ..., K_x, ..., K_(l-1)
    • 对于这些新词中的每一个，将其添加到 HashTable H 中，键为 K_x，值为 K（原始错误词）

现在对于正确单词列表中的每个单词 C，：

  • 对于每个 C，检查 HashTable H 中是否存在键 C。
  • 如果 HashTable H 中存在键 C，则输出与 C 关联的值 C'：由于这些值都来自 INCORRECT 单词列表，因此我们必须找到一个不正确的单词，通过交换两个连续的字母，将其变成正确的单词单词。
  • 输出每个这样的 C'

由于 l 是一个固定数字（它必须是，否则你可以同时将 l 和 n 增长到无穷大，否则没有线性时间算法），你有以下运行时复杂性：

  • 遍历不正确的单词列表需要线性时间
  • 为不正确单词列表中的每个单词生成新单词需要恒定的时间 l
  • 将每个（新词，K）添加到哈希表 H 需要恒定的时间
  • 遍历正确的单词列表需要线性时间
  • 根据 HashTable H 检查正确单词列表中的每个单词需要恒定的时间

因此这是 O(n) 运行时间。

于 2012-10-21T05:22:21.623 回答
0 
findTypos(List CORRECT_LIST,
List INCORRECT_LIST,
List TYPOS_OUTPUT_LIST) {
 boolean INCORRECT_LIST_EMPTY = false  

 for each element in CORRECT_LIST {  
    TYPOS = computeTypos(element)  
    for each typo in TYPOS  
        if(INCORRECT_LIST.contains(typo)) {  
            INCORRECT_LIST.remove(typo)  
            TYPOS_OUTPUT_LIST.add(typo)  
        }  
        if(INCORRECT_LIST.size() == 0) {  
            INCORRECT_LIST_EMPTY = true;  
            break;  
        }  
    }  
    if(INCORRECT_LIST_EMPTY) {  
        break;  
    }  
 }
 return TYPOS_OUTPUT_LIST;
}
于 2012-10-21T05:43:49.743 回答
0

这是单一交换案例的解决方案。我假设每个单词只有一个交换。因此，对于 word algorithm，algo[ir]thm是一个有效的错字；而[la]go[ir]thm无效。

让我们调用正确的单词列表A和另一个列表B。

  1. 从 list 中创建一个包含不正确单词的哈希表。像这样的哈希函数HBB
    Σ(a i *10 i ); 其中 0 <= i < a.length，a i = 索引 i 处字符的 int 值
    这是O(l).

2.迭代A。

（假设 base 1 索引）

错字= []
对于 i = 1 到 A.length
  对于 j = A[i].length 到 2
    临时 = 交换（A[i]，j，j-1）
    哈希 = getHash(temp)
    如果（ HB .has（哈希））
      错字。添加（临时）
返回错字

你看到两个循环了吗？他们执行多少次？让我们做数学

a 1 .length + a 2 .length + .. + al .length - l
（减号是因为我们实际上在每个单词中都少了一个）
= length_of_all_characters_the_list_A - l

但是我如何获得订单？嗯，大 O 是上边界，所以

O(l*max(A[i].length)
=> O(l*m)
于 2012-10-21T05:47:43.357 回答