时间戳

首页 > 解决方案 > 查找字符串 S2 所花费的时间

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

问题描述

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

给定一个字符串 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.

我确信通过运行两个循环很容易在二次方中做到这一点，但这不是一个有效的解决方案。有什么想法可以改进吗？

标签： javaalgorithmdata-structures

解决方案

大编辑

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

另一个编辑

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

原始答案

如果您依赖于已排序的事实S1并且每个字符与其邻居的值相差 1，您可以计算字符之间的差异并将其S2相加

例如：
S2 = cba

添加a到S2以获取起始值：
S2 = acba

对于 中的每个字符c1及其右邻c2，S2
distance += |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)空间。

推荐阅读