1

我正在尝试编写一个简单的python算法来解决这个问题。你能帮我弄清楚为什么我的代码不起作用：

问题：

Jakub 正在尝试一维键盘。它由单行键组成。任意两个相邻键之间的距离为 1。每个键包含一个不同的英文字母。Jakub 只用一根手指在键盘上打字。他想知道在输入给定单词时他必须移动手指的最小总距离是多少。

例如，如果键盘的唯一一行是“qwertyuiop”，而 Jakub 想要输入单词“potter”，他将不得不将手指从“p”移动到“o”（距离 1），从“o”移动到“ t'（距离 4），从 't' 到 't'（距离 0），从 't' 到 'e'（距离 2）和从 'e' 到 'r'（距离 1），总距离1 + 4 + 0 + 2 + 1 = 8。

给你一个字符串键盘和一个字符串单词，描述键盘和 Jakub 想要写的单词。返回他必须移动手指才能在键盘上键入单词的最小距离。

我的代码：

def typingDistance (keyboard, word):
    a=keyboard.find(word[0][:1])
    res=0
    for i in word:
        if keyboard.find(i) != a:
            res+=abs(a-i)
        a = keyboard.find(i)
    return res
4

1 回答 1

5

问题是你正在做a-iwhere iis the letter 而不是a-position. 把位置分解出来，瞧！

def typingDistance (keyboard, word):
    a = keyboard.find(word[0][:1])

    res=0
    for i in word:
        position = keyboard.find(i)
        if position != a:
            res += abs(a-position)
        a = position
    return res

请注意，这word[0]是一个字母，因此word[0][:1]是同一个字母（因为"a"[:1]只是“a”）。所以你可以忽略它：

另请注意，您不必这样做if position != a，因为无论如何距离都会0：

def typingDistance (keyboard, word):
    a = keyboard.find(word[0])

    res=0
    for i in word:
        position = keyboard.find(i)
        res += abs(a-position)
        a = position
    return res

最后请注意，最好在开始时进行映射，映射字母→它们在键盘上的索引，这样您就可以避免keyboard.find过于频繁地调用。这只会在word比 长得多的情况下才有帮助keyboard，但是在学习时养成一个好习惯：

def typingDistance(keyboard, word):
    letter2position = {letter: keyboard.index(letter) for letter in keyboard}

    a = letter2position[word[0]]
    res=0
    for i in word:
        position = letter2position[i]
        res += abs(a-position)
        a = position
    return res

请注意，letter2position[...]只需替换keyboard.find(...); 如果您意识到函数是输入到输出的映射，那么这是有道理的，所以letter2position它只是一个预先计算所有结果的函数。

于 2013-09-22T23:17:56.227 回答