दो अलग-अलग ऐरे 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]
