1859. Sorting the Sentence
Approach
Split sentence, sort by trailing digit (word position), strip digits and rejoin.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Split sentence, sort by trailing digit (word position), strip digits and rejoin.
// Time: O(n log n) Space: O(n)
public class Solution
{
public string SortSentence(string s)
{
string[] words = s.Split(' ');
Array.Sort(words, (a, b) => a[a.Length - 1] - b[b.Length - 1]);
StringBuilder sb = new StringBuilder(Trim(words[0]));
for (int i = 1; i < words.Length; ++i)
sb.Append(" ").Append(Trim(words[i]));
return sb.ToString();
}
private string Trim(string s)
{
return s.Substring(0, s.Length - 1);
}
}