`
zuroc
  • 浏览: 1290125 次
  • 性别: Icon_minigender_1
  • 来自: 江苏
社区版块
存档分类
最新评论

相似单词

 
阅读更多
给你一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词。现在给你一个字典,用户输入一个单词,让你根据字典找出这个单词有多少个兄弟单词。
....
from itertools import tee,izip
from collections import defaultdict

def pairwise(iterable):
    a, b = tee(iterable)
    for elem in b:
        break
    return izip(a, b)

buf_array=[]
buf_no={}
key_from_id=0
def add_to_buf(word):
    global key_from_id,buf_array

    if len(word)==1:
        pass
        #TODO

    for pos,pair in enumerate(pairwise(word)):

        if len(buf_array)<pos+1:
            buf_array.append(defaultdict(set))
        pos_dict=buf_array[pos]
       
        key=list(pair)
        key.sort()
        key="".join(key)
        if key not in buf_no:
            buf_no[key]=key_from_id
            key_from_id+=1
       
        key=buf_no[key]

        pos_dict[key].add(word)


def find_in_buf(word):
    global key_from_id,buf_array

    if len(word)==1:
        pass
        #TODO
   
    exist = []
    for pos,pair in enumerate(pairwise(word)):
        if len(buf_array)<pos+1:
            return     
        pos_dict=buf_array[pos]

        key=list(pair)
        key.sort()
        key="".join(key)
       
        if key not in buf_no:
            continue
       
        key=buf_no[key]
        if key not in pos_dict:
            continue
       
        exist.append(pos_dict[key])
   
    count_dict=defaultdict(int)
    for i_set in exist:
        for i in i_set:
            count_dict[i]+=1
    result=[]
    min_match = len(word)-3
    for k,v in count_dict.iteritems():
        if v>=min_match:
            result.append(k)
    return result

add_to_buf("1234")
add_to_buf("ABCD")
add_to_buf("CABD")

print find_in_buf("ACBD")
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics