Version strings look like "1.2.10": one or more non-negative integers separated by dots. Sort versions in ascending order comparing component by component numerically (so "1.10" is newer than "1.9"). When one version's components are a prefix of another's, the shorter one comes first ("1.2" before "1.2.0"). Identical strings keep their original relative order.
Return the sorted list of the original strings.
Examples
Input: versions = ["1.10", "1.2", "1.2.1", "1.2.0", "0.9"]
Output: ["0.9", "1.2", "1.2.0", "1.2.1", "1.10"]
Constraints
0 <= len(versions) <= 5 * 10**4, each with at most 6 components, each component< 10**6- Components may have leading zeros (
"01"equals"1"). - Target complexity: O(n log n).
Goals
- Parse dotted version strings into numeric components
- Sort by tuples so numeric comparison replaces string comparison
- Place a shorter version before any version it is a prefix of