Given an array of strings arr[], consisting of N strings each representing dot separated numbers in the form of software versions.
Input: arr[] = {“1.1.2”, “0.9.1”, “1.1.0”} Output: “0.9.1” “1.1.0” “1.1.2” Input: arr[] = {“1.2”, “0.8.1”, “1.0”} Output: “0.8.1” “1.0” “1.2”
Approach: Follow the steps below to solve the problem:
- Create a function to compare two strings.
- Store strings into a vector.
- In order to compare two dot separated strings S1 and S2, iterate up to the length min(S1, S2) + 1 and compare each numerical parts of the string and sort accordingly.
- Repeat the above steps for each pair of string and sort the array accordingly.
Below is the implementation of above idea:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Compares two stringsint check(const string& a, const string& b){ int al = a.length(); int bl = b.length(); int i = 0, j = 0; while (i < al && j < bl) { if (a[i] == b[j]) { ++i; ++j; } else if (a[i] > b[j]) { return 1; } else return -1; } if (i == al && j == bl) return 0; if (i == al) return -1; return 1;}// Function to split strings based on dotsvector<string> getTokens(const string& a){ vector<string> v; string s; // Stringstream is used here for // tokenising the string based // on "." delimiter which might // contain unequal number of "."[dots] stringstream ss(a); while (getline(ss, s, '.')) { v.push_back(s); } return v;}// Comparator to sort the array of stringsbool comp(const string& a, const string& b){ // Stores the numerical substrings vector<string> va, vb; va = getTokens(a); vb = getTokens(b); // Iterate up to length of minimum // of the two strings for (int i = 0; i < min(va.size(), vb.size()); i++) { // Compare each numerical substring // of the two strings int countCheck = check(va[i], vb[i]); if (countCheck == -1) return true; else if (countCheck == 1) return false; } if (va.size() < vb.size()) return true; return false;}// Driver Codeint main(){ vector<string> s; s.push_back("1.1.0"); s.push_back("1.2.1"); s.push_back("0.9.1"); s.push_back("1.3.4"); s.push_back("1.1.2"); s.push_back("1.1.2.2.3"); s.push_back("9.3"); // Sort the strings using comparator sort(s.begin(), s.end(), comp); // Display the sorted order for (int i = 0; i < s.size(); i++) { cout << s[i] << endl; } cout << endl; return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class comp implements Comparator<String>{ // Compares two Strings static int check(String a, String b) { int al = a.length(); int bl = b.length(); int i = 0, j = 0; while (i < al && j < bl) { if (a.charAt(i) == b.charAt(j)) { ++i; ++j; } else if (a.charAt(i) > b.charAt(j)) { return 1; } else return -1; } if (i == al && j == bl) return 0; if (i == al) return -1; return 1; } // Function to split Strings based on dots static String[] getTokens(String a) { return (a.split(".")); } // Comparator to sort the array of Strings public int compare(String a, String b) { // Stores the numerical subStrings String[] va = getTokens(a); String[] vb = getTokens(b); // Iterate up to length of minimum // of the two Strings for (int i = 0; i < Math.min(va.length, vb.length); i++) { // Compare each numerical subString // of the two Strings int countCheck = check(va[i], vb[i]); if (countCheck == -1) return -1; else if (countCheck == 1) return 1; } if (va.length < vb.length) return -1; return 1; }}class GFG{ // Driver Code public static void main(String[] args) { ArrayList<String> s = new ArrayList<String>(); s.add("1.1.0"); s.add("1.2.1"); s.add("0.9.1"); s.add("1.3.4"); s.add("1.1.2"); s.add("1.1.2.2.3"); s.add("9.3"); // Sort the Strings using comparator Collections.sort(s, new comp()); // Display the sorted order for (int i = 0; i < s.size(); i++) { System.out.println(s.get(i)); } }}// This code is contributed by phasing17. |
Python3
# Python3 Program to implement# the above approachimport functools# Compares two stringsdef check(a, b): al = len(a); bl = len(b); i = 0 j = 0; while (i < al and j < bl) : if (a[i] == b[j]) : i += 1; j += 1; elif (a[i] > b[j]): return 1; else: return -1; if (i == al and j == bl): return 0; if (i == al): return -1; return 1;# Function to split strings based on dotsdef getTokens(a): v = [] # Stringstream is used here for # tokenising the string based # on "." delimiter which might # contain unequal number of "."[dots] ss = a.split('.'); for s in ss: v.append(s); return v;# Comparator to sort the array of stringsdef comp(a, b): # Stores the numerical substrings va = [] vb = []; va = getTokens(a); vb = getTokens(b); # Iterate up to length of minimum # of the two strings for i in range(min(len(va), len(vb))): # Compare each numerical substring # of the two strings countCheck = check(va[i], vb[i]); if (countCheck == -1): return False; elif (countCheck == 1): return True; if len(va) < len(vb): return False; return True;# Driver Codes = [];s.append("1.1.0");s.append("1.2.1");s.append("0.9.1");s.append("1.3.4");s.append("1.1.2");s.append("1.1.2.2.3");s.append("9.3");# Sort the strings using comparators.sort(key = functools.cmp_to_key(comp));# Display the sorted orderprint(*s, sep = '\n')# This code is contributed by phasing17 |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;public class comp : IComparer<string>{ // Compares two strings static int check(string a, string b) { int al = a.Length; int bl = b.Length; int i = 0, j = 0; while (i < al && j < bl) { if (a[i] == b[j]) { ++i; ++j; } else if (a[i] > b[j]) { return 1; } else return -1; } if (i == al && j == bl) return 0; if (i == al) return -1; return 1; } // Function to split strings based on dots static List <string> getTokens(string a) { List<string> v = new List<string>(a.Split('.')); return v; } // Comparator to sort the array of strings public int Compare(string a, string b) { // Stores the numerical substrings List<string> va, vb; va = getTokens(a); vb = getTokens(b); // Iterate up to length of minimum // of the two strings for (int i = 0; i < Math.Min(va.Count, vb.Count); i++) { // Compare each numerical substring // of the two strings int countCheck = check(va[i], vb[i]); if (countCheck == -1) return -1; else if (countCheck == 1) return 1; } if (va.Count < vb.Count) return -1; return 1; }}class GFG{ // Driver Code public static void Main(string[] args) { List<string> s = new List<string>(); s.Add("1.1.0"); s.Add("1.2.1"); s.Add("0.9.1"); s.Add("1.3.4"); s.Add("1.1.2"); s.Add("1.1.2.2.3"); s.Add("9.3"); // Sort the strings using comparator s.Sort(new comp()); // Display the sorted order for (int i = 0; i < s.Count; i++) { Console.WriteLine(s[i]); } }}// This code is contributed by phasing17. |
Javascript
// JS Program to implement// the above approach// Compares two stringsfunction check(a, b){ let al = a.length; let bl = b.length; let i = 0, j = 0; while (i < al && j < bl) { if (a[i] == b[j]) { ++i; ++j; } else if (a[i] > b[j]) { return 1; } else return -1; } if (i == al && j == bl) return 0; if (i == al) return -1; return 1;}// Function to split strings based on dotsfunction getTokens(a){ let v = [] // Stringstream is used here for // tokenising the string based // on "." delimiter which might // contain unequal number of "."[dots] let ss = a.split('.'); for (let s of ss) v.push(s); return v;}// Comparator to sort the array of stringsfunction comp(a, b){ // Stores the numerical substrings let va = [], vb = []; va = getTokens(a); vb = getTokens(b); // Iterate up to length of minimum // of the two strings for (var i = 0; i < Math.min(va.length, vb.length); i++) { // Compare each numerical substring // of the two strings let countCheck = check(va[i], vb[i]); if (countCheck == -1) return false; else if (countCheck == 1) return true; } if (va.length < vb.length) return false; return true;}// Driver Code let s = []; s.push("1.1.0"); s.push("1.2.1"); s.push("0.9.1"); s.push("1.3.4"); s.push("1.1.2"); s.push("1.1.2.2.3"); s.push("9.3"); // Sort the strings using comparator s.sort(comp); // Display the sorted order console.log(s.join("\n"))// This code is contributed by phasing17 |
Output
0.9.1 1.1.0 1.1.2 1.1.2.2.3 1.2.1 1.3.4 9.3
Time complexity: O(n*log(n)*len) where n is the number of strings in the array and len is the length of longest string in the array
Auxiliary space: O(len)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
