Cách tìm khoảng cách ngắn nhất đến ký tự trong chuỗi cho trước trong C#

Tạo 2 mảng leftDis và rightDis. leftDis lưu khoảng cách duyệt từ trái, rightDis từ phải. Khi gặp ký tự mục tiêu, đặt = 0. Cuối cùng lấy min của hai mảng.

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(N)

Ví dụ

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;
                rightDis[i] = count;
            }
            else if (count != int.MaxValue)
            {
                count++;
                rightDis[i] = count;
            }
        }
        count = int.MaxValue;
        for (int i = n - 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[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 ss = "lovecode";
    char c = 'e';
    var res = s.ShortestDistanceToCharacter(ss, c);
    foreach (var item in res)
    {
        Console.WriteLine(item);
    }
    // Output: 3,2,1,0,1,2,1,0
}

Kết quả đầu ra

3
2
1
0
1
2
1
0