java - 查找字符串 S2 所花费的时间

Question

假设您有一个特殊的键盘，所有键都排在一行中。键盘上的字符布局由长度为 26 的字符串 S1 表示。S1 的索引从 0 到 25。最初索引为 0。要键入字符，我们需要移动所需字符的索引。将索引从 i 移动到 j 所花费的时间是 |j-i|哪里||是绝对值。

给定字符串 s1 和 s2，描述输入字符串 s2 所花费的时间。

给定两个字符串 S1 和 S2，其中 S1 = abcdeghijklmnopqrstuvwxyz

s2=cba

并从索引 0 ('A') 开始查找键入 cba 所花费的时间。

index of c = 2
count = 2 - 0
count = 2 + 1 (c to b )
count = 2 + 1(c to b) + 1 (b to a)
count returned should be 4.

我确信这很容易通过运行两个循环在二次方程式中实现，但这不是一个有效的解决方案。我有什么改进方法吗？

Answer 1

大编辑

实际上，根据定义，S1 是固定长度并且不依赖于输入 S2 这一事实意味着@Amiy 的答案是正确的。因为 indexOf 只在 S1 上运行，所以它最多需要 26 步。 O(26n) = O(n)。我的答案只是一个较低的常数，根据变化在 1n 到 2n 之间运行。

---

另一个编辑

对于一般情况，S1 也是一个变量输入，我们不能对其做出任何假设，请参阅@user000001 在O(nlogm) 中的哈希解决方案。

---

原始答案

如果您依赖于 S1 已排序并且每个字符与其相邻字符相差 1 的事实，您可以只计算 S2 中字符之间的差异> 总结一下

例如:
S2 = cba

将a添加到S2以获得起始值:
S2 = acba

对于S2中的每个字符c1及其右邻c2，
距离 += |c1 - c2|

---

如果您不依赖于 S1 已排序这一事实(这可能是您正在寻找的)，您可以将 S1 的值索引到一个数组中，然后应用与上述类似的算法:

例如:

S1 = "qwertyuiopasdfghjklzxcvbnm"
arr = array of size 26
let i = 0
for each character c in S1:
    arr[c - 'a'] = i++

然后，调整算法:

S2 = "cba"
let distance = 0
for each character c1 and its right-neighbour c2 in S2:
    distance += |arr[c1 - 'a'] - arr[c2 - 'a']|

---

两种算法都在 O(n) 中解决问题，而第一个使用 O(1) 空间，第二个使用 O(n)空间。