การหาความห่างสั้นที่สุดถึงตัวอักษรในสตริงด้วย C#

สร้างอาร์เรย์ leftDis และ rightDis leftDis เก็บระยะทางจากซ้าย rightDis เก็บระยะทางจากขวา เมื่อเจอตัวอักษรเป้าหมาย บันทึกตำแหน่ง สุดท้ายหาค่าต่ำสุด (Min) ของทั้งสองอาร์เรย์

Time Complexity: O(N)

Space Complexity: O(N)

ตัวอย่างโค้ด

public class Arrays
{
    public int[] ShortestDistanceToCharacter(string s, char c)
    {
        int n = s.Length;
        int[] leftDis = new int[n];
        int[] rightDis = new int[n];
        // เริ่มต้นค่า
        for (int i = 0; i < n; i++)
        {
            leftDis[i] = int.MaxValue;
            rightDis[i] = int.MaxValue;
        }
        // สแกนจากซ้ายไปขวา
        int count = int.MaxValue;
        for (int i = 0; i < n; i++)
        {
            if (s[i] == c)
            {
                count = 0;
            }
            if (count != int.MaxValue)
            {
                rightDis[i] = count;
                count++;
            }
        }
        // สแกนจากขวาไปซ้าย
        count = int.MaxValue;
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == c)
            {
                count = 0;
            }
            if (count != int.MaxValue)
            {
                leftDis[i] = count;
                count++;
            }
        }
        // หาค่าต่ำสุด
        int[] ans = new int[n];
        for (int i = 0; i < n; i++)
        {
            ans[i] = Math.Min(leftDis[i], rightDis[i]);
        }
        return ans;
    }
}

static void Main(string[] args)
{
    Arrays s = new Arrays();
    string str = "lovecode";
    char c = 'e';
    var res = s.ShortestDistanceToCharacter(str, c);
    foreach (var item in res)
    {
        Console.WriteLine(item);
    }
}

ผลลัพธ์

3
2
1
0
1
2
1
0