C++ 字符串中重复字符的最小距离

在计算机科学中，经常会遇到找到字符串中重复字符的最小距离的问题。它涉及到找到给定字符串中任意两个相同字符之间的最小距离。例如，在字符串”minimum distance”中，两个’i’之间的最小距离为2，因为它们分别在位置1和3出现。这个问题可以用不同的编程语言解决，包括C++。

在本教程中，我们将学习一种使用C++实现的高效解决这个问题的算法。让我们开始学习一些新的令人兴奋的东西吧！

问题陈述

目标是在给定非空字符串S（长度为N）中找到两个重复字符之间的最小间隔。如果字符串S中没有重复的字符，则函数应返回-1。

让我们通过示例来理解这个问题陈述。

示例1

输入：

S = "tutorialspoints"; N = 15

输出

The shortest distance between repeating characters is 1.

解释：在给定的字符串 “tutorialspoints” 中，字母 ‘t’ 出现在索引 0 和 2 处。这两个 ‘t’ 之间的最小距离是1，这是程序的输出。

示例2

输入

S = "programming"; N = 11

输出结果

The shortest distance between repeating characters is 1.

解释：在给定的字符串”programming”中，重复字符之间的最小距离是”0″，因为字母’m’连续出现两次，索引分别为6和7。

算法

最小距离的算法在给定字符串中相同的重复字符之间:

第1步：定义一个名为’calculateShortestDistanceBetweenRepeatingChars’的函数，该函数接受一个 ‘std::string’ 和它的长度 ‘len’ 作为输入参数。

第2步：将最小距离’minDistance’设置为字符串的长度，假设没有重复字符。

第3步：对于字符串中的每个字符’i’，遍历所有后续字符’j’。

第4步：如果’i’和’j’是相同的字符，并且它们之间的距离小于当前的最小距离，更新最小距离为新的距离。

第5步：如果’minDistance’仍然等于字符串的长度，则表示没有找到重复的字符，因此返回-1。

第6步：否则，从’minDistance’中减去1，得到重复字符之间的最短距离，并返回该值。

第7步：在’main()’函数中，定义一个字符串’str’和它的长度’len’，然后调用’calculateShortestDistanceBetweenRepeatingChars’函数，并将结果存储在’shortestDistance’中。

第8步：输出结果：如果’shortestDistance’等于-1，则输出”在字符串中没有找到重复的字符。”，否则输出”重复字符之间的最短距离是’shortestDistance’。”。

现在，在理解了算法之后，可以使用C++实现上述算法。我们将通过一个示例来实现它。所以让我们开始吧！

示例

使用C++实现上述算法

下面的C++程序计算给定字符串中两个重复字符之间的最短距离，并输出结果。它通过迭代字符串中的每个字符并将其与所有后续字符进行比较来实现这一点，同时跟踪到目前为止找到的重复字符之间的最小距离。如果没有找到重复字符，则程序返回-1，否则输出重复字符之间的最短距离。

#include <iostream>
#include <string>
#include <algorithm>

int calculateShortestDistanceBetweenRepeatingChars(const std::string& str, int len) {
   // Set the minimum distance to the length of the string, assuming no repeating characters
   int minDistance = str.length();
   // For every character present in the given string
   for (int i = 0; i < len; i++) {
      // For each character that comes after it
      for (int j = i + 1; j < len; j++) {
         // If the characters are identical and the gap between them is smaller than the current minimum distance
         if (str[i] == str[j] && (j - i) < minDistance) {
            // Update the minimum distance
            minDistance = j - i;
            // As this value would be the minimum possible, break from the loop
            break;
         }
      }
   }
   // If the minimum distance is still the length of the string, no repeating characters were found
   if (minDistance == str.length()) {
      return -1;
   } else {
      // Subtract one from the minimum distance to get the shortest distance between repeating characters
      return minDistance - 1;
   }
}
int main() {
   // Example input
   std::string str = "tutorialspoint";
   int len = str.length();
   // Calculate the shortest distance between repeating characters
   int shortestDistance = calculateShortestDistanceBetweenRepeatingChars(str, len);
   if (shortestDistance == -1) {
      std::cout << "No repeating characters found in the string.\n";
   } else {
      std::cout << "The shortest distance between repeating characters is " << shortestDistance << ".\n";
   }
   return 0;
}

输出

The shortest distance between repeating characters is 1.

结论

总而言之，我们讨论了在给定字符串中找到相同重复字符之间最小距离的问题。我们详细解释了问题陈述，并给出了两个输入输出示例。我们还提供了一个使用嵌套循环实现有效解决方案的C++程序，用于比较每对字符。通过按照程序中提出的算法，我们可以轻松找到给定字符串中相同重复字符之间的最小距离。这个问题在各种编程面试和编程比赛中都常见到，通过理解本教程中提出的解决方案，我们可以更好地准备自己应对这样的挑战。