2টি ভিন্ন অ্যারে লেফটডিস এবং রাইটডিস তৈরি করুন। বাম দিক থেকে সরানো হলে লেফটডিস মান সংরক্ষণ করবে। ডান থেকে সরানো হলে রাইটডিস সংক্ষিপ্ততম মান সংরক্ষণ করবে। যখনই অক্ষরটি পূরণ হয় অ্যারেতে অক্ষরের অবস্থান যোগ করুন। শেষ ধাপে উভয় অ্যারের সর্বনিম্ন গণনা করুন।
সময়ের জটিলতা − 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]
