Problem: Given a string and a character in the given string, return an array of integers say result where result[i] will have the shortest distance of i to the given character's index in the input string.
Example:
Input: s = "nishant", c = "n" Output: [0,1,2,2,1,0,1]
Approach: Approach can be understood easily by just looking at the implementation as it is fairly a very straight forward problem.
Implementation in C#:
public static int[] ShortestToChar(string s, char c)
{
List<int> charPositions = new List<int>();
for (int i = 0; i < s.Length; ++i)
{
if (s[i] == c)
{
charPositions.Add(i);
}
}
int[] result = new int[s.Length];
int currCharIndex = 0;
int nextCharIndex = currCharIndex + 1 == charPositions.Count ? -1 : currCharIndex + 1;
for (int i = 0; i < s.Length; ++i)
{
if (i <= charPositions[currCharIndex] || nextCharIndex == -1)
{
result[i] = Math.Abs(charPositions[currCharIndex] - i);
}
else
{
if (Math.Abs(charPositions[currCharIndex] - i) >= charPositions[nextCharIndex] - i)
{
result[i] = charPositions[nextCharIndex] - i;
currCharIndex = nextCharIndex;
nextCharIndex = currCharIndex + 1 == charPositions.Count ? -1 : currCharIndex + 1;
}
else
{
result[i] = Math.Abs(charPositions[currCharIndex] - i);
}
}
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment