cxxpython9
diff --git a/‎.idea/workspace.xml‎
Lines changed: 80 additions & 43 deletions b/‎.idea/workspace.xml‎
Lines changed: 80 additions & 43 deletions
diff --git a/‎BinarySearch.py‎
Lines changed: 20 additions & 0 deletions b/‎BinarySearch.py‎
Lines changed: 20 additions & 0 deletions
diff --git a/‎CheckErrorWord.py‎
Lines changed: 44 additions & 0 deletions b/‎CheckErrorWord.py‎
Lines changed: 44 additions & 0 deletions
@@ -0,0 +1,20 @@
+# 实现一个二分查找
+# 输入:一个顺序list
+# 输出: 待查找的元素的位置
+def binarySearch(alist, item):
+    first = 0
+    last = len(alist) - 1
+
+    while first <= last:
+        mid = (first + last)//2
+        print(mid)
+        if alist[mid] > item:
+            last = mid - 1
+        elif alist[mid] < item:
+            first = mid + 1
+        else:
+            return mid+1
+    return -1
+
+test = [0, 1, 2, 8, 13, 17, 19, 32, 42]
+print(binarySearch(test, 3))
@@ -0,0 +1,44 @@
+# 网传鹅厂面试题,英语单词拼写检查算法
+# 比如输入hello, 却错误的输入了hellu, 找出出错的字母
+# 感谢知乎知友@Lee Shellay
+
+# 对词典中的每个词, 逐刺逐字母拓展Trie, 单词完结处结点用END符号标识
+END = '$'
+
+def make_trie(words):
+    trie = {}
+    for word in words:
+        t = trie
+        for c in word:
+            if c not in t:
+                t[c] = {}
+            t = t[c]
+        t[END] = {}
+    return trie
+
+# 容错查找
+# 实质上是对Trie的深度优先搜索,每一步加深时就消耗目标词的一个字母
+# 当搜索到达某个结点时,分为不消耗容错数和消耗容错数的的情形,继续搜索知道目标词为空。
+# 搜索过程中,用path记录搜索路径,该路径及为一个词典中存在的词,作为纠错的参考
+# 最终结果即为诸多搜索停止位置的结点路径的并集
+def check_fuzzy(trie, word, path='', tol=1):    #tol为容错数
+    if word == '':
+        return [path] if END in trie else []
+    else:
+        p0 = []
+        if word[0] in trie:
+            p0 = check_fuzzy(trie[word[0]], word[1:], path+word[0], tol)
+        p1 = []
+        if tol > 0:
+            for k in trie:
+                if k != word[0]:
+                    p1.extend(check_fuzzy(trie[k], word[1:], path+k, tol-1))
+        return p0 + p1
+
+
+# 测试代码
+words = ['hello', 'hela', 'dome']
+t = make_trie(words)
+print(t)
+print(check_fuzzy(t, 'hellu'))
+print(check_fuzzy(t, 'healu', tol=2))