时间戳

首页 > 解决方案 > 相同字符之间的最小距离

c++ - 相同字符之间的最小距离

问题描述

我想找出两个相同字符之间的最小距离（它们之间的字符数）。（如果存在多个返回最小的一个）

例如

1) Input = patent
<br>
output=2 (as t and t are 2 char away)
<br>
2) Input = pattern
<br>
output=0 (t and t are next to each other)<br>
3)Input = ababdbbdhfdksl
<br>
output=0 as (b and b are consecutive)

标签： c++c++14

解决方案

散列是我能想到的一种方法。

假设：

  1. 输入中只有 26 个可能的字符 [az]。
  2. 如果没有两个相同的字符，则返回 INF。

基本理念：

我们只需要记住找到当前字符的最后一个索引，这将是与该位置的字符对应的最小距离（假设该字符不再出现）。我们可以使用变量来存储全局最小值。

方法：

  1. 创建一个大小为 26 的数组来存储找到它的每个字符的最后一个索引。让我们调用数组lastIndex []，

    • lastIndex [0]：存储找到字符“a”的最后一个索引。
    • lastIndex [1]：存储找到字符“b”的最后一个索引。
    • lastIndex [25]：存储找到字符“c”的最后一个索引。

  2. 将lastIndex的元素初始化为 -1。

  3. 将变量minDistance初始化为 INF。
  4. 遍历所有元素。让position表示与lastIndex中的当前字符相对应的索引。如果 lastIndex[position] 不等于 -1，则计算currentMinDistance = (idx - lastIndex[position] - 1)。如果currentMinDistance小于minDistance，则将minDistance分配给currentMinDistance。将lastIndex[position]更新为idx。
  5. 返回minDistance。

您可以在更新minDistance时扩展此方法以存储元素的索引。

这是该方法的代码：

int getMinimumDistanceBetweenSameCharcters(const string &s){
    int lastIndex[26];
    for( int idx = 0; idx < 26 ; ++idx ){
        lastIndex[idx] = -1;
    }
    int minDistance = INT_MAX;
    for( int idx = 0; idx < s.size() ; ++idx ){
        int position = s[idx] - 97; // ASCII
        if( lastIndex[position] != -1 && (idx - lastIndex[position] - 1) < minDistance ){
            minDistance = idx - lastIndex[position] - 1;
        }
        lastIndex[position] = idx;
    }
    return minDistance;
}

时间复杂度 - O(n)，其中 n 是字符串的大小。
空间复杂度 - O(1)，假设唯一字符的数量有限。

推荐阅读