在键盘上找出字母之间的距离

Question

我正在尝试寻找“qwerty”键盘上两个字母之间的最小距离。例如，如果我评估字母q和w，最小距离应该是1，因为它们在键盘上相邻，而字母q和e的最小距离应该是2，因为它们只相隔两个位置。

我正在尝试创建一个用于实现此操作的字典。

coords = {
    'qw':1, 'qe':2, 'qr':3, 'qt':4, 'qy':5, 'qu':6, 'qi':7, 'qo':8, 'qp':9, 'qa':1, 'qs':2, 'qd':3, 
    'qf':4, 'qg':5, 'qh':6, 'qj':7, 'qk':8, 'ql':9, 'qz': 2, 'qx':3, 'qc':4, 'qv':5, 'qb':6, 'qn':7, 'qm':8,
    'q1':1, 'q2':1, 'q3':2, 'q4':3, 'q5':4, 'q6':5, 'q7':6, 'q8':7, 'q9':8}

接着可以这样做，为了找到每两个字母之间的最小距离值（我只针对字母q的单侧配对进行了计算）。

sentence = 'qw'
grams = [sentence[i:i+N] for i in range(len(sentence)-N+1)]
[coords[i] for i in grams]

- Lucas Dresl

---

主要问题在于你所称之为距离和“coords”的概念是具有误导性的，因为它们是相对于w的。因此，你应该处理绝对数据而不是相对数据来回答问题。 - cards

Answer 1

与其手动保存所有可能的字母组合，我认为保存每个字母的位置并计算距离会更容易。

例如，q是(0, 0)，w是(1, 0)，a是(0, 1)，以此类推。第一个元素代表X坐标，第二个元素代表Y坐标，从左上角开始。

彼此之间的距离可以很容易地自动化计算（我选择了曼哈顿距离，您可以根据需要选择距离计算算法）。

key_positions = {"q": (0, 0), "w": (1, 0), ...}
def dist(c1, c2):
    pos1 = key_position[c1]
    pos2 = key_position[c2]
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

- minolee

Answer 2

你可以为每个键创建一个节点，并为每个相邻关系创建一条边，然后在运行BFS时即可实时获取距离（或者如果你愿意的话，可以预先计算字典中的距离）。在这样一个小图上，BFS将非常快速。

- Dave

Answer 3

你可以使用find()函数来查找查询字符串的第一个和第二个字母的索引，然后计算这两个索引之间的差值，以获取距离，就像这样：

text = 'qwerty'
query = 'qy'

index1 = text.find(query[0])
index2 = text.find(query[1])
distance = index2 - index1

- koegl