จะค้นหาระยะทางที่สั้นที่สุดไปยังอักขระในสตริงที่กำหนดโดยใช้ C # ได้อย่างไร

สร้าง 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);
   }
}

ผลลัพธ์

[3,2,1,0,1,2,1,0]