Given a sentence S of size N where each word is a concatenation of a numeric part followed by a bunch of characters. The task is to arrange the words in increasing order of their numeric part.
Examples:
Input: S = “24-amazing 7-coders 11-are”
Output: coders are amazing
Explanation: order of numeric values are 7, 11, 24.
So they are arranged accordinglyInput: S = “19-Love 10-I 2001-cricket”
Output: I Love cricket
Approach: The approach of the solution is based on the concept of min-heap. Split the strings on the basis of spaces and put them in the heap. At last pop them from the heap and print them in order. That will give the desired solution.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>#include <boost/algorithm/string.hpp>using namespace std;// For arranging words on the basis// of numeric part// Function to arrange the sentencestring solve(string str){ vector<string> arr; boost::split(arr, str, boost::is_any_of(" ")); priority_queue<pair<int,string>> pq; for(int i = 0; i < arr.size(); i++) { string s = arr[i]; string N = ""; int a = 0; while(s[a] != '-') { N += s[a]; a += 1; } int num = stoi(N); string word = arr[i].substr(a + 1); pq.push(make_pair(num, word)); } string sb = ""; while (0 < pq.size()) { sb = pq.top().second + " "+sb; pq.pop(); } return sb;}// Driver codeint main(){ string S = "19-Love 10-I 2001-cricket"; string ans = solve(S); cout<<ans;}// This code is contributed by Pushpesh raj |
Java
// Java code to implement above approachimport java.util.*;class GFG { // For arranging words on the basis // of numeric part public static class pair implements Comparable<pair> { int num; String word; pair(int num, String word) { this.num = num; this.word = word; } public int compareTo(pair o) { return this.num - o.num; } } // Function to arrange the sentence public static String solve(String str) { String[] arr = str.split(" "); PriorityQueue<pair> pq = new PriorityQueue<>(); for (int i = 0; i < arr.length; i++) { String s = arr[i]; String N = ""; int a = 0; while (s.charAt(a) != '-') { N += s.charAt(a); a++; } int num = Integer.parseInt(N); String word = s.substring(a + 1); pq.add(new pair(num, word)); } StringBuilder sb = new StringBuilder(); while (pq.size() > 0) { pair p = pq.remove(); sb.append(p.word); sb.append(" "); } sb.deleteCharAt(sb.length() - 1); return sb.toString(); } // Driver code public static void main(String[] args) { String S = "19-Love 10-I 2001-cricket"; String ans = solve(S); System.out.println(ans); }} |
Python3
# python3 code for the above approach# For arranging words on the basis# of numeric part# Function to arrange the sentencedef solve(str): arr = str.split(" ") pq = [] for i in range(0, len(arr)): s = arr[i] N = "" a = 0 while (s[a] != '-'): N += s[a] a += 1 num = int(N) word = s[a + 1:] pq.append([num, word]) pq.sort() sb = "" k = 0 while (k < len(pq)): sb += pq[k][1] + " " k k += 1 return sb# Driver codeif __name__ == "__main__": S = "19-Love 10-I 2001-cricket" ans = solve(S) print(ans) # This code is contributed by rakeshsahni |
C#
// C# code to implement above approachusing System;using System.Text;using System.Collections.Generic;class GFG { // Pair class for arranging words based on numeric part public class pair : IComparable<pair> { public int num; public string word; public pair(int num, string word) { this.num = num; this.word = word; } public int CompareTo(pair other) { return this.num - other.num; } } // Function to arrange the sentence public static string solve(string str) { string[] arr = str.Split(" "); List<pair> pq = new List<pair>(); for (int i = 0; i < arr.Length; i++) { string s = arr[i]; string N = ""; int a = 0; while (s[a] != '-') { N += s[a]; a++; } int num = Convert.ToInt32(N); string word = s.Substring(a + 1); pq.Add(new pair(num, word)); } pq.Sort(); StringBuilder sb = new StringBuilder(); foreach (pair p in pq) { sb.Append(p.word); sb.Append(" "); } sb.Remove(sb.Length - 1, 1); return sb.ToString(); } // Driver code public static void Main(string[] args) { string S = "19-Love 10-I 2001-cricket"; string ans = solve(S); Console.WriteLine(ans); }} |
Javascript
<script> // JavaScript code for the above approach // For arranging words on the basis // of numeric part // Function to arrange the sentence function solve(str) { let arr = str.split(" "); let pq = [] for (let i = 0; i < arr.length; i++) { let s = arr[i]; let N = ""; let a = 0; while (s.charAt(a) != '-') { N += s.charAt(a); a++; } let num = parseInt(N); let word = s.slice(a + 1); pq.push({ 'first': num, 'second': word }); } pq.sort(function (a, b) { return a.first - b.first }) let sb = ""; let k = 0; while (k < pq.length) { sb += pq[k].second + " "; k++; } return sb } // Driver code let S = "19-Love 10-I 2001-cricket"; let ans = solve(S); document.write(ans); // This code is contributed by Potta Lokesh </script> |
Output
I Love cricket
Time Complexity: O(N log N)
Auxiliary Space: O(N)
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!
