如何使用C#找到给定字符串中字符的最短距离？

Z时代
2024-01-10
分类：综合

创建 2 个不同的数组 leftDis 和 rightDis。当从左方向移动时，leftDis 将存储该值。当从右边移动时，rightDis 将存储最短的值。每当遇到字符时，将字符的位置添加到数组中。在最后一步计算两个数组的最小值。

时间复杂度-O(n)

空间复杂度-O(n)

示例

public class Arrays{
   public int[] ShortestDistanceToCharacter(string s, char c){
      int stringLength = s.Length;
      int[] leftDis = new int[s.Length];
      int[] rightDis = new int[s.Length];
      leftDis = Enumerable.Range(0, s.Length).Select(n => int.MinValue).ToArray();
      rightDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray();
      int count = int.MaxValue;
      for (int i = 0; i < rightDis.Length; i++){
         if (s[i] == c){
            count = 0;
            rightDis[i] = count;
         }
         else{
            if (count != int.MaxValue){
               count++;
               rightDis[i] = count;
            }
         }
      }
      count = int.MaxValue;
      for (int i =leftDis.Length- 1; i >= 0; i--){
         if (s[i] == c){
            count = 0;
            leftDis[i] = count;
         }
         else{
            if (count != int.MaxValue){
               count++;
               leftDis[i] = count;
            }
         }
      }
      int[] ans = new int[stringLength];
      for (int i = 0; i < stringLength - 1; i++){
         ans[i] = Math.Min(leftDis[i], rightDis[i]);
      }
      return ans;
   }
}
static void Main(string[] args){
   Arrays s = new Arrays();
   string ss = "lovecode";
   char c = 'e';
   var res = s.ShortestDistanceToCharacter(ss, c);
   foreach (var item in res){
      Console.WriteLine(item);
   }
}