สมมติว่ามีคีย์บอร์ดพิเศษที่มีปุ่มทั้งหมดอยู่ในแถวเดียว ดังนั้นถ้าเรามีสตริงความยาว 26 ที่บ่งบอกเลย์เอาต์ของคีย์บอร์ด (ดัชนี 0 ถึง 25) เริ่มต้นนิ้วมือของเราอยู่ที่ดัชนี 0 เพื่อพิมพ์ตัวอักษร เราต้องย้ายนิ้วไปที่ดัชนีของตัวอักษรถัดไป เวลาที่ใช้ในการย้ายนิ้วจากดัชนี i ไป j คือ |i - j| ดังนั้นถ้าเราต้องการพิมพ์สตริง เราต้องกำหนดฟังก์ชันเพื่อคำนวณว่าใช้เวลาเท่าไรในการพิมพ์ด้วยนิ้วเดียว ดังนั้นถ้าลำดับอินพุตคือ "abcdefghijklmnopqrstuvwxyz" และคำคือ "hello" ผลลัพธ์จะเป็น 20 เพราะจาก a ไป h คือ 7 แล้ว h ไป e คือ 3 แล้ว e ไป l คือ 7 แล้ว l ไป l คือ 0 และ l ไป o คือ 3 รวมเป็น 7 + 3 + 7 + 3 = 20
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ −
- สร้างแมปชื่อ d และ z := 0
- for i ในช่วง 0 ถึงความยาวของสตริงเลย์เอาต์ k
- d[k[i]] := i
- ans := 0
- สำหรับแต่ละตัวอักษร i ใน word −
- ans := ans + |d[i] - z|
- z := d[i]
- คืนค่า ans
ตัวอย่าง (Python)
มาดูการนำไปใช้เพื่อความเข้าใจที่ดีขึ้น −
class Solution(object):
def calculateTime(self, k, w):
d = {}
z = 0
for i in range(len(k)):
d[k[i]] = i
ans = 0
for i in w:
ans += abs(d[i] - z)
z = d[i]
return ans
ob1 = Solution()
print(ob1.calculateTime("abcdefghijklmnopqrstuvwxyz", "hello"))
อินพุต
"abcdefghijklmnopqrstuvwxyz" "hello"
ผลลัพธ์
20
