Tạo 2 mảng khác nhau leftDis và rightDis. LeftDis sẽ lưu giá trị khi di chuyển từ hướng trái. RightDis sẽ lưu giá trị ngắn nhất khi được di chuyển từ bên phải. Bất cứ khi nào ký tự được đáp ứng, hãy thêm vị trí của ký tự vào mảng. Trong bước cuối cùng, hãy tính toán giá trị tối đa của cả hai mảng.
Độ phức tạp về thời gian - O (n)
Độ phức tạp của không gian - O (n)
Ví dụ
public class Arrays{
public int[] LongestDistanceToCharacter(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.Max(leftDis[i], rightDis[i]);
}
return ans;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
string ss = "lovecode";
char c = 'e';
var res = s.LongestDistanceToCharacter(ss, c);
foreach (var item in res){
Console.WriteLine(item);
}
} Đầu ra
[2147483647,2147483647,2147483647,0,3,2,3,0]